Xu Xiangyang, Zhangfang Lei

(Hebei University of Faculdade de Ciências e Tecnologia da Ciência da Informação e Engenharia, Shijiazhuang 050000)

Particle Swarm Optimization (PSO) algoritmo em uma nuvem ambiente de computação, aspecto agendamento de tarefas é amplamente utilizado. Para algoritmo é fácil cair em ótimo local, defeitos de convergência lenta, a partir do conceito básico, acrescentando melhorias no peso algoritmo dinâmico inércia e estratégias perturbações externas para melhorar a capacidade de busca local de PSO para melhorar o algoritmo de velocidade de convergência tarde iterativo e pesquisa precisão Finalmente experimento Cloudsim irá implementar o novo algoritmo com outros algoritmos tarefas resultam do número total de iterações de comparação, o novo algoritmo supera as deficiências da PSO algoritmo pode efetivamente equilibrar capacidades de pesquisa globais e locais, o tempo de conclusão da tarefa relativamente pequeno.

Cloud computing; agendamento de tarefas; otimização de enxame de partículas; Cloudsim

CLC: TP301 código do documento: A DOI: 10,19358 / j.issn.2096-5133.2018.08.007

formato de citação: . Xu Xiangyang, agendamento de tarefas Zhangfang Lei [J] computação algoritmo nuvem CAOS PSO com base em tecnologia da informação e segurança da rede, 2018,37 (8): 27-30.

agendamento de tarefas com base em caótica enxame perturbação de partículas

algoritmo de otimização no ambiente de computação da nuvem

Xu Xiangyang, Zhang Fanglei

(Escola de Ciência da Informação e Engenharia da Universidade de Hebei de Ciência e Tecnologia, Shijiazhuang 050000, China)

Resumo: Enxame de Partículas (PSO) algoritmo é amplamente utilizado no agendamento de tarefas no ambiente de cloud computing. Visando o problema que o algoritmo de enxame de partículas é fácil cair em ótimo local e tem baixa taxa de convergência, este trabalho começa com o conceito básico, acrescenta peso de inércia dinâmica e estratégia de perturbação externa no enxame de partículas algoritmo para melhorar o local,-otimização. Este algoritmo pode resolver os problemas de convergência lenta e precisão baixo busca .Finalmente, Cloudsim plataforma de simulação é utilizado para testar. Comparando os resultados do número de iterações entre o novo algoritmo e outros algoritmos no tempo de execução da tarefa, novo algoritmo supera a deficiência de otimização por enxame de partículas, e pode efetivamente equilibrar a procura global e busca local. o tempo de conclusão da tarefa é observável mais curto.

Palavras-chave: Cloud computing; agendamento de tarefas; otimização de enxame de partículas; Cloudsim

0 Introdução

Nuvem tarefa de computação algoritmo de programação sob o ambiente afeta diretamente a eficiência da experiência do usuário na qualidade do serviço, enquanto a maioria dos algoritmos de otimização tradicionais não conseguem atender a demanda atual, muitos pesquisadores propuseram algoritmo de colônia de formigas, algoritmo genético classe inteligente heurística algoritmo. O estudo principal é algoritmo de enxame de partículas otimização inteligente algoritmo (Particle Swarm Optimization, PSO). Modelo de Particle Swarm é uma área nos últimos anos para fazer o alimento de uma ave para encontrar comida, para reduzir o tempo de busca e aumentar a taxa. Desde o algoritmo PSO tem alguns parâmetros, computacionalmente eficientes, procurando rápido, fácil programação e amplamente utilizado e assim por diante, tantos estudiosos aplicados pesquisa sobre ambiente algoritmo de agendamento de tarefas de computação em nuvem.

Fatores de muitos especialistas e estudiosos continuam a analisar e estudar o agendamento de tarefas influência, temos desenvolvido muitos programas importantes neste algoritmo. [1] A partícula de núcleo generalizada e trajectórias das partículas estreitas, através da análise de bi-centro PSO, melhorar a precisão e a convergência taxa das partículas do algoritmo. [2] No multi-tasking para atender a qualidade de usuário do serviço, propõe um multi-QoS restrições algoritmo de otimização por enxame de partículas discretas é. [3] A ligação de partícula de Pareto solução óptima conjunto de programação de fluxo de trabalho, a resolução de conflitos problema de três objectivo optimização enxame híbrido. [4] propõe um grupo de partículas parcialmente aprendizagem inversa e o algoritmo de optimização de aprendizagem, aumentar a diversidade da população de partículas preparadas por aprendizagem inversa, algoritmo de redução localmente situação óptima. [5] por forma adaptativa ajustando o peso total inércia para o equilíbrio velocidade de convergência e convergência do algoritmo, para melhorar o algoritmo de desempenho.

optimização enxame de partícula será normalmente combinada com outra optimização enxame de partículas. [6] algoritmo genético transversal, as características de variação do algoritmo genético, com uma optimização modificado misturado enxame de partículas, de partículas especiais de mutação, mas também melhora a precisão da busca de partícula, reduzindo significativamente o tempo para completar a tarefa. [7] ligao Ant Colony Algoritmo PSO e as suas vantagens, de modo que pela partícula enxame grupo partícula iterações iniciais produziram bons partículas iniciais de geração de feromonas, em seguida, aplicado algoritmo feromona colónia, a solução óptima finalmente .

Este artigo analisa as deficiências dos princípios básicos e por enxame de partículas por enxame de partículas algoritmo para resolver problemas de programação, para as deficiências de melhorias PSO no peso de inércia, algoritmo de resolução de uma precisão "prematuro" e atrasado baixo convergência nas primeiras edições e adicionou perturbação caótica, dada pela função de adaptação, o número de tarefas diferentes para o estudo, o total de algoritmos de alinhamento de tempo a conclusão da tarefa, e para observar o número de iterações.

otimização 1 Introdução enxame de partículas

algoritmo de otimização enxame 1.1 de partículas para os princípios básicos

Tradicional PSO é um algoritmo inteligente pela American psicólogo KENNEDY J e engenheiros elétricos EBERHART RC em 1995, apresentado em conformidade com peixes, aves forrageamento actividade [8]. No entanto, o PSO tradicional ajustar a velocidade da partícula não existe, o algoritmo reduz a capacidade de busca local e busca global. Assim, a fim de compensar a falta de partícula tradicional algoritmo de optimização enxame, SHI Y e EBERHART RC sob a premissa deste algoritmo introduz inércia peso, e um estudo em profundidade, a velocidade das partículas já não é uma única taxa fixa de [9-10] .

Todos grupo de partículas de partículas tem a sua própria posição, velocidade e sentido de movimento. Cada partícula é um indivíduo, as partículas individuais si aparecem depois de experimentar um número de iterações a solução óptima é chamado valor extremo indivíduo pbest, o grupo será constituído por partículas populações globalmente solução óptima, ou seja, extremo gbest global. Todas as partículas irão encontrar a melhor localização, essa partícula irá procurar a solução ideal, que é determinado por uma função de fitness é otimizado. PSO PSO algoritmo tem de ser inicializado, e, em seguida, a solução ideal por partículas atualizar repetidamente a sua posição e velocidade na solução óptima individual e global, depois de iterações repetidas, finalmente, obter extremos.

Nota o número de partículas no grupo de partículas é N, o movimento das partículas no espaço d-dimensional, a posição e a velocidade das partículas fórmula k i tempo como se segue.

função de adaptação é determinada através da optimização da partícula e a localização óptima do melhor fórmula global está como se segue.

locais ideais:

localização global ideal:

Antes de obter dois valores extremos, as partículas irão pesquisar de acordo com a fórmula, a posição e velocidade de actualização:

Em que, d é o número de partículas na dimensão do espaço de busca; K é o número de iteração, também se refere ao tempo corrente; C1, C2 para o número das duas normais, isto é, factor de aprendizagem, também chamada factor de aceleração; , entre 0 e 1 é dois um número aleatório entre.

é o peso de inércia, SHI Y EBERHART R C e a introdução das massas de inércia na optimização do enxame de partículas, isto é,

= max- (max-min) x k / Kmax (7)

Em que, max, min são o peso mínimo inércia máxima e, k é o número de partículas no momento de iterações, Kmax é o número máximo de partículas de iterações.

De acordo com o princípio da PSO, os principais parâmetros que afetam o algoritmo PSO são: escala de PSO, peso de inércia, aprender o fator de maior velocidade e movimento de partículas e assim por diante.

algoritmo 1.2 PSO aplicação e emissão

algoritmo PSO tem sido amplamente aplicado para resolver o problema multi-objectivo, em todas as áreas de otimização dinâmica, otimização de parâmetros, otimização combinatória e outros problemas de otimização, e aplicado controle sistema fuzzy, sistemas de distribuição de energia, redes neurais, o fluxo loja de agendamento, biomédica, etc. . Mas com a nuvem ambiente para resolver o problema de otimização de agendamento de tarefas de computação, haverá óptimo local, questões de convergência lenta atraso; semelhança de outros classe inspirada algoritmo inteligente, um algoritmo não pode resolver todo o problema esta otimização. PSO algoritmo é mais adequado para resolver o problema contínuo para o problema de programação de tarefa discreta não pode ser um bom jogo para os seus pontos fortes, é necessário melhorar ainda mais o desempenho do algoritmo baseado em PSO algoritmo, para remover existem os algoritmos de escalonamento de tarefas no processo de defeitos, conseguir assim melhores resultados práticos, melhorar a utilização de recursos e qualidade da plataforma de serviços, para melhorar a experiência do usuário.

estudo de optimização enxame 2 Melhoria da partícula

Em aplicações reais, o algoritmo de otimização pode não só melhorar a lado, geralmente eles são múltiplos problema de otimização objetivo, mas otimização multi-objetivo em muitos casos, contraditórias e conflitantes, de modo a melhor otimização só pode ser de acordo com a situação real, pesam cada objecto obtido extremos relativos. Este trabalho feito em tempo para a tarefa principal com base nos méritos do desempenho do algoritmo.

2.1 Função de Fitness

As partículas têm de se adaptar aos méritos determinação do valor de posição actuais. Agendamento de tarefas é o menor tempo para completar a tarefa mais eficiente completar a tarefa menos tempo, o valor da função objetivo maior é a aptidão da população de partículas, melhor. Portanto, devemos primeiro definir a função de fitness, e na fórmula (1) xkid substitutos função de aptidão f (x), em busca de fitness.

R tem recursos, s partulas, o tempo de execução da tarefa sobre o recurso i com j T (i, j) representa:

O tempo total para completar a tarefa da seguinte forma:

função de aptidão é definida como:

2.2 Cálculo do peso de inércia

algoritmo PSO para resolver o problema no problema de programação de tarefas é propenso a cedo melhor local, reduzir a precisão de pesquisa de pós-global. Portanto, a fim de equilibrar a capacidade de busca global e local, nos pesos de correlação de melhoria pesada compreende pesos adaptativos, pesos aleatórios e afins. Neste papel, o peso inércia exponencial co melhorado método de peso. valores de peso inércia maior, capacidade de pesquisa global vai melhorar, mas as capacidades de busca local irá deteriorar-se, se o valor de menor, busca local vai aumentar, mas a capacidade de busca global pobres. De acordo com problemas de peso inércia, este artigo vai inércia expressões de peso, como mostrado:

= min + exp [- ((max-min) x k / Kmax) 2] (10)

A partir da equação acima, onde será exponencialmente nas iterações iniciais para manter um valor maior, de modo que o PSO reforçada no iterações iniciais capacidade de pesquisa global; na iteração tarde capaz de manter uma pequenas e graduais mudanças no valor, final de melhorar o algoritmo de busca local, acelerar a taxa de convergência. Com base em estudos anteriores, este peso inércia no intervalo de [0,4-0,9].

2,3 CAOS

Chaos em um determinado intervalo, etc. pode atravessar toda a probabilidade nenhum estado de repetição, o algoritmo no processo de resolver a tarefa, as outras partículas guiaria população porque muito poucas melhores partículas rapidamente perto da partícula ideal, a partícula se este não alcançar o ótimo global excelente, pois pode levar a algoritmo de otimização local. partícula caótico sensível aos valores iniciais, é possível de acordo com as regras internas do caos aleatoriamente através de todas as partículas. Portanto, a fim de evitar partículas preso em uma "prematura", necessidade de adicionar um distúrbio externo, de modo que as partículas podem quebrar otimização local.

Quando as partículas de presença precoce de um distúrbio externo para o mecanismo de PSO "prematura". fórmula CAOS utilizado no presente documento:

Algoritmo de fluxo mostrado na Fig.

Um fluxograma para implementação do algoritmo da FIG.

3 Experimental simulação e análise

Neste estudo, o uso de computação em nuvem como uma ferramenta experimental plataforma Cloudsim-3.0, MyEclipse para o desenvolvimento de ferramentas, Java linguagem de desenvolvimento. Os procedimentos experimentais básicos: ambiente experimental de construção, inicialização Cloudsim, criar um centro de dados, agente de serviço, defina os parâmetros dos recursos de máquinas virtuais e tarefas, e estender o algoritmo de agendamento de tarefas chamando, começar Cloudsim, e os resultados finalmente experimentais.

experimento 3.1 simulação

experimento Cloudsim com o ambiente de implantação, expanda o novo algoritmo em DatacenterBroker, o número de tarefas foram definidas para 50100200500, o experimento vai melhorar o algoritmo e PSO (SPSO) experimento de simulação, e estes dois algoritmos para completar a tarefa o caso quando o número de iterações de análise e comparação. Neste artigo, os parâmetros do algoritmo mostrado na Tabela 1.

Tabela 1 SPSO melhorou configurações algoritmo e parâmetros de

3.2 Comparação de resultados e discussão

Tabela 1 Os parâmetros definidos experimentais, para garantir a precisão do experimento, cada experiência foi realizada 20 vezes, e, finalmente, em média, de 20 experiências foram comparados. experiência comparativa, no caso dos dois algoritmos não é o número de tarefas ao mesmo tempo, o número mínimo de iterações é concluída quando o tempo O resultado experimental mostrado na Fig. 2 a 5.

A figura 2 é uma série de tarefas quando o tempo total de conclusão da tarefa 50

A figura 3 é o número de tarefas a conclusão da tarefa de tempo total de 100

A FIG 4 é um número de tarefas de tempo total de 200 conclusão da tarefa

Quando o número de tarefas 500 na Fig. 5 como o tempo total de conclusão da tarefa

Pode ser desenhada por comparação dos resultados experimentais acima descritos, no algoritmo de início NPSO iterativo é mais forte do que a capacidade de convergência SPSO, mas o número de tarefas no mesmo algoritmo NPSO do que o tempo total para completar a tarefa NPSO algoritmo utilizado diminuiu, e a convergência do último é forte por programas de comparação que o algoritmo melhorado tem uma melhor eficiência, melhores condições para melhorar a experiência do usuário em aplicações práticas.

4 Conclusão

Muitos pesquisadores para algoritmo de programação de tarefa levada a cabo muitos estudos, este PSO papel melhorado com base em nossos predecessores. Ao optimizar o peso de inércia, e adicionou perturbação caótico durante a enxame de partículas no estado de partículas que atravessam, de acordo com a função dada de fitness, o desempenho do novo algoritmo são comparados com outros algoritmos de escalonamento. Os resultados experimentais mostram que o regime proposto efetivamente reduz o tempo de execução de tarefas, reduzindo os custos de consumo de recursos, viável.

Referências

. [1] casos lata sopa Liubing Xiang, Yang Jing, et centro PSO bis [J] Investigação e Desenvolvimento, 2012, 49 (5) Computador: 1086-1094.

[2] Wang Yue, Liu Yaqiu, Guo Jifeng, et algoritmo de escalonamento al.QoS em nuvem computação baseado na optimização enxame de partículas discretas [J] .computer Engenharia, 2017,43 (6): 111-117.

[3] Du Yanming, ambiente CIÊNCIAS Xiao Jianhua nuvem de fluxo de trabalho grupo partícula objectivo agendamento algoritmo híbrido [J] Computer Science, 2017,44 (8), com base em: 252-259.

[4] Xiaxue Wen, TOPOGRAFIA Clain elevado, e por isso têm uma aprendizagem inversa aprendizagem capacidade PSO parcial [J] Computer Journal, 2015,38 (7): 1397-1407.

[5] de acordo com qualquer rodada, Liu Pei-yu, um novo dinâmico adaptativo Xuesu Zhi cultura PSO [J] Computer Research, 2013, 30 (11): 3240-3243.

[6] Wang Bo, Zhang Xiaolei nuvem pesquisa computando algoritmo de agendamento de tarefas enxame de partículas genética [J] Engenharia de Computação e Aplicações, 2015,51 (6) Baseado em: 84-88.

[7] Wang Dengke, Zhong PSO baseada em nuvem e ACO do algoritmo de escalonamento [J] aplicações informáticas e software, 2013,30 (1): 290-293.

[8] KENNEDY J, otimização de enxame EBERHART R C. Particle [C] // Proceedings da Conferência IEEE em redes neurais, Perth, Austrália, 1995: 1942-1948.

[9] SHI Y, R. EBERHART partícula de modificação enxame optimizador [C] // Proceedings do IEEE Conferência ICEC, Anchorage, 1998: 69-73.

[10] EBERHART R C, SHI Y. pesos Comparando inércia e factores de constrição em optimização enxame de partículas [C] // Proceedings of Congress 2000 em Evolutionary Computation, 2000. IEEE, 2002: 84-88.

(Data de recebimento: 2018/04/14)

Sobre o autor:

Xu Xiangyang (1967-), do sexo masculino, mestre, professor, direção de pesquisa principais: informação de gestão de rede.

Zhangfang Lei (1990-), do sexo feminino, estudantes de pós-graduação, interesses de pesquisa incluem: gestão de rede de informação.