MyGa : manual de utilização
Contents
1. o 1 3 2 4 e ref 3 para a defini o dessa muta o Esta muta o definida pelo par metro b Um pequeno valor de b 1 favorece a explora o e um valor elevado acelera a busca local typem nonun uma varia o da muta o n o uniforme que frequentemente d os melhores resultados Escapar dos m nimos locais no caso das muta es do tipo nonuni e nonun2 os par metros nbstag e kb permitem a sa da de alguns m nimos locais nos quais o programa pode se encontrar aprisionado De fato se nenhuma melhora na melhor solu o conseguida ap s nbstag gera es o valor do par metro b torna se naquela gera o kb b com kb lt 1 Isto tem como efeito o aumento da for a de muta o e favorece a explora o no espa o de busca e Busca local definida pelos par metros RafLoc e nbtot Este procedimento pouco eficaz e resulta frequentemente numa converg ncia prematura Para evitar deixe RafLoc NOrafloc e Sele o dois tipos de sele o s o poss veis sele o por roleta types rs sele o por roleta estoc stica e Elitismo ativado se felit 1 Je desativado se elit 0 O elitismo consiste em assegurar que n o haja decr scimo da melhor solu o a cada gera o Na pr tica se para uma dada gera o n nenhum indiv duo melhor que a solu o da gera o anterior n 1 o melhor indiv duo da gera o n 1 transferido para a gera o n e Nichos Niching esta t c2. ada Depois de realizadas as etapas da se o 3 2 essa se o detalha os arquivos parameter inc e param dat 3 3 1 O arquivo parameter inc Nesse arquivo h 4 par metros a serem determinados e popsize o tamanho da popula o de cada gera o Este programa apresentou melhores performances com um tamanho igual a 10 e dimx a dimens o do espa o de busca e genemax o n mero m ximo de gera es antes que o programa seja finalizado e genemaxmut um par metro que determina o decrescimento da for a de muta o do tipo nonun2 definida na se o 3 3 2 Este par metro dever ser genemaxmutZgenemax Para um decr scimo mais lento da for a de muta o experimente genemaxmut 1 5 genemax por exemplo 3 3 2 O arquivo param dat e Exibi o na tela o par metro affichecran pode assumir os valores 0 1 2 e 3 Para cada n vel informa es suplementares s o adicionadas 0 nenhuma exibi o na tela 1 exibi o da ltima gera o e da melhor solu o 2 exibe se o valor da melhor solu o encontrada em cada gera o 3 a gera o inicial exibida e Salvar o par metro savefich pode assumir os valores 0 1 e 2 0 nenhuma grava o Essa n o uma alternativa interessante se voc al m disso utilizar affichecran 0 1 a melhor solu o salva arquivo resultat dat e o estado dos c lculos arquivo restart dat tamb m salvo para uma retomada eventual dos c lculos 2 sa
3. MyGa manual de utiliza o Adel BEN HAJ YEDDER 19 de Novembro de 2002 Tradu o do franc s para o portugu s por Dr Adriano Pinto Mariano Dra Caliane Bastos Borba Costa Laborat rio de Otimiza o Projeto e Controle Avan ado LOPCA Respons vel Prof Dr Rubens Maciel Filho Faculdade de Engenharia Qu mica FEQ Universidade Estadual de Campinas UNICAMP Brasil 01 de Julho de 2008 1 Introdu o Este programa uma implementa o de um algoritmo gen tico em c digo real escrito em Fortran Os tipos de operadores desenvolvidos s o bastante limitados e somente alguns operadores conhecidos por sua efici ncia foram incorporados O objetivo desse programa quando foi desenvolvido era de ter um algoritmo gen tico em Fortran de f cil utiliza o e eficiente para o problema para o qual ele foi escrito O programa distribu do a fim de fornecer aos programadores em Fortran uma ferramenta para testar e ou utilizar uma otimiza o com algoritmos gen ticos em seus pr prios problemas Este programa fornecido sem qualquer garantia nem qualquer suporte al m desse documento Se voc o utiliza voc o UNICO respons vel por sua utiliza o e em particular pelos resultados que ele gere e por aquilo que voc faz em seguida 2 Instala o Sistema operacional O programa foi escrito e testado para Linux Entretanto deve funcionar em outros sistemas do tipo N X dependendo de pequenas modifica es C
4. cer os limites com os quais se efetuar a busca Troque 10 pelo valor de dimx nas duas linhas e troque 1 D1 e 1 Dl respectivamente para o limite inferior e superior dos intervalos de busca Recompile e reinicie o programa De maneira geral para se efetuar uma busca em E xmins xmax XX XMiNndimx XMAX dim os limites devem ser escritos da seguinte maneira xmin xmin 7 XM Ndimx XMAX xmax XMOAX Gimxs 3 2 Utiliza o simplificada Para utilizar rapidamente MyGa para minimizar uma outra fun o proceda da seguinte maneira 1 Mude no arquivo parameter inc a dimens o do espa o de busca dimx O valor deve ser o n mero de par metros a serem otimizados 2 Escreva no arquivo func f sua fun o a minimizar Esta fun o deve receber um vetor x de dimens o dimx e retornar o valor da fun o fx Se sua fun o corresponde a um programa que voc utiliza com suas pr prias nota es e nomes de vari veis o melhor guardar suas vari veis a serem otimizadas no vetor x Assim voc mant m os nomes de suas vari veis e a rotina func f s v o vetor x e o valor fx Da mesma maneira se voc tem que transferir par metros para a sua fun o ou fazer inicializa es voc deve fazer estas opera es sem modificar a estrutura da rotina func f 3 Mude no arquivo param dat os limites do espa o de busca como indicado na se o 3 1 4 Compile com make e execute o programa 3 3 Utiliza o avan
5. elhor uma maneira que funciona em muitos casos com restri es simples e Cruzamento Os par metros que correspondem ao operador cruzamento s o pc typec alpha nbmultip e tm A probabilidade de se aplicar um cruzamento entre cromossomos dada por pc Quatro tipos de cruzamento s o poss veis ec bary cruzamento baric ntrico com o par metro alpha a definindo os 2 pesos a e 1 o typec baryaP cruzamento baric ntrico onde o coeficiente a escolhido aleatorimente no intervalo 0 1 typec muitip cruzamento multipontos com o n mero de pontos de corte dado por nbmultip m Jonde m um inteiro 0 lt m lt dimux typec sby cruzamento dito SBX com o par metro alpha a definindo a forma da lei de probabilidade utilizada Tome a 1 ou 2 por exemplo No caso onde os dois pais s o muito pr ximos a probabilidade de muta o do filho ver o item sobre a muta o abaixo aumentada e torna se igual tm O objetivo de provocar muta o nas duas crian as geradas que se pare am muito com seus pais e Muta o Os par metros deste operador s o pm typem b nbstag e kb A probabilidade de aplicar uma muta o a um indiv duo dada por pm Tr s tipos de muta o s o poss veis typem varnor muta o gaussiana com um desvio tipo o que decresce em dire o a zero com o curso das gera es typem nonuni muta o n o uniforme ver ref 1 Se
6. ite o arquivo MyGa f e mude no come o do programa a linhafirandom 1 para irandom time Refer ncias 1 A Ben Haj Yedder Optimisation num rique et Contr le optimal applications en chimie mol culaire PhD thesis Ecole Nationale des Ponts et Chauss es 2002 2 Z Michalewicz Genetic algorithms data structure evolution programs Springer 1999 3 Mourad Sefrioui Algorithmes Evolutionnaires pour le calcul scientifique Application la m canique des fluides et l lectromagnetisme PhD thesis Universit Pierre et Marie Curie 1998
7. lva a melhor solu o a cada gera o arquivo bestx dat e o valor da fun o correspondente arquivo bestfx dat e Testes de parada dois tipos de testes de parada s o poss veis Quando voc quiser fazer testes de parada o programa pode parar quando a solu o solx alcan ada ou quando o valor m nimo de f solfx atingindo No geral o programa p ra quando o n mero de itera es m ximo restartfin atingido Solu o alcan ada coloque o par metro typeconv solx solx x1 Xgimxs eps s onde x7 Xdimx s o as coordenadas da solu o e e define a precis o Valor m nimo alcan ado coloque o par metro typeconv solfx solfx minimum eleps s jonde minimum o valor do minimo da fun o f caso geral coloque o par metro typeconv je restartfin iterfin onde iterfin a gera o na qual o programa deve parar e deve ser iterfin lt genemax Mais precisamente restartini iterdebut c restartfin iterfin definem a gera o do come o e a gera o do fim do programa Para um primeiro c lculo deve se ter restartini 1 Nesse caso a popula o inicial gerada aleatoriamente no espa o de busca E xmin xmax x X XMiNndimx XMAX dim Para recuperar um antigo c lculo de uma gera o gen lt genemax utilize e restartfin iterfin Jcom gen lt iterfin lt genemax Nesse caso o c lculo ser retomado com a popula o que ser relida no arquivo restart dat criad
8. nica permite favorecer a explora o espacial penalizando os indiv duos que se encontram na mesma regi o do espa o Os par metros s o niche q sigmaniche e alphaniche Ver ref 3 pra os detalhes dessa t cnica 1 para ativar esta t cnica e O para desativ la para utilizar a norma p no c lculo da dist ncia sigmaniche o deve ser lt 1 alphaniche a para determinar a intensidade do nicho Com a pequeno a lt 1 o nicho pouco intenso e com a grande o nicho bastante intenso m o O e Escalonamento ver ref 1 Se o 1 3 2 4 e ref 2 para os detalhes Os par metros s o scaling scal scalingvar scalvarl scalvar2 e scalvarp Os dois primeiros par metros para o primeiro escalonamento 5 possibilidades e os quatro ltimos para um segundo escalonamento vari vel facultativo em fun o do tempo 5 possibilidades O escalonamento que deu os melhores resultados o o scaling que escolhido por Ecaling sigma Os outros escalonamentos poss veis s o exp em e xexp em xe log em log l x e puiss em x Estes mesmos escalonamentos s o adaptados para o escalonamento vari vel 4 Coment rios e Inicializa o do gerador de n meros aleat rios atualmente o gerador de n meros aleat rios inicializado sempre da mesma maneira Como conseq ncia duas execu es sucessivas do programa produzem o mesmo resultado Para inicializar o gerador de outra maneira ed
9. o a partir do primeiro c lculo Nota se que um c lculo feito em dois tempos n o sempre o mesmo que um c lculo feito em uma nica etapa visto que o arquivo restart dat cont m unicamente a popula o a qual o c lculo deve retomar mas n o cont m outras informa es Este detalhe n o tem muita import ncia salvo nos casos onde s o feitos testes de performance ou onde se busca a reprodu o perfeita de um c lculo antigo e Inicializa o da popula o A popula o inicial gerada aleatoriamente no caso geral Quando o par metro initpop m com 0 lt m lt dimx o programa vai ler m indiv duos no arquivo initx dat que v o substituir m indiv duos da popula o aleat ria Nesse caso voc deve introduzir estes m indiv duos no arquivo initx dat com uma coordenada por linha Isto pode ser til se voc introduzir indiv duos que lhe pare am pr ximos da solu o Mas aten o converg ncia prematura que pode ser provocada por um individuo muito bom aquele que voc adicionou em rela o aos outros e Espa o de busca Como indicado na se o 3 1 o espa o de busca definido pelos limites Jam ami xminamo e FM M smaxamz O programa n o leva em conta qualquer outro tipo de restri o Uma maneira simples de levar em conta outras restri es de penalizar fortemente uma viola o de restri o na fun o de custo f N o a melhor maneira de levar em conta as restri es mas na falta de outra alternativa m
10. ompilador O programa est escrito em Fortran 77 Voc deve ent o utilizar um compilador compat vel com o Fortran 77 Para definir o compilador edite o arquivo Makefile e modifique a primeira linha O compilador padr o default g77 Extra o de arquivos e compila o Digite as seguintes linhas de comando gt gunzip MyGa 1 0 tar gz gt tar xvf MyGa 1 0 tar gt cd MyGa 1 0 gt make 3 Utiliza o A otimiza o no MyGa feita minimizando se uma fun o f x calculada em func f com x um vetor de dimens o dimx definido em parameter inc 3 1 Exemplos O arquivo func f fornecido cont m 5 exemplos de fun es testes O primeiro exemplo o da fun o esfera com dimens o dimx 10 Para testar este exemplo digite gt make gt Myga A evolu o da melhor solu o ao longo das gera es ao mesmo tempo exibida na tela e salva nos arquivos bestfx dat o valor da fun o e bestx dat O arquivo resultat dat cont m o resultado final obtido Para os testes com outros exemplos preciso editar o arquivo func f e outro exemplo escolhido mudando se a linhafgoto 10 para onde num e 10 20 30 40 50 Edite em seguida o arquivo parameter inc para escolher a dimens o dimx em fun o do caso escolhido Voc pode deixar a dimens o inalterada salvo para o caso num 40 onde a dimens o deve ser igual a 2 Ent o edite o arquivo param dat mudando as duas linhas xmin 10 1 D1 xmax 10 1 D1 para forne
Download Pdf Manuals
Related Search