Rotas e Mutação - Algoritmos Genéticos (AG)

Programação Java
#1

Olá pessoal!

Estou com uma dificuldade com um trabalho… onde:

Os veículos partem inicialmente de João Pessoa, onde está instalada a Central de
Trituração (CT) estudada, coletam os pneus e os descarregam novamente em
João Pessoa.
b) Todos os veículos possuem as mesmas capacidades, rendimento, e tempo de
viagem para o transporte de pneus.
c) O peso de cada município, na elaboração das rotas, estará associado à
quantidade de pneus coletados e a distância até a CT.
d) Os pneus devem ser coletados de uma só vez, não havendo possibilidade de um
segundo caminhão auxiliar na coleta, a não ser quando um caminhão vazio não
conseguir transportar a carga de um só município.
e) Um veículo não consegue transportar mais de 2160 pneus de uma vez.

Deverá implementar e executar, uma aplicação que faça uso a metaeuristica (AG))

Observações importantes:
Cada versão deve ser executada cinco vezes sendo que, cada execução, deve
fazer uso de uma semente distinta, cujo conjunto a ser utilizado é o seguinte:
1970641, 1014029, 1824607, 1354051 e 993893.

Consegui, gerar as rotas… só que esta dando erro. e a parte da mutação e da comparação Nao consigo fazer.

Alguem pode me ajudar por favor!

#2

Oi.

Sempre que postar códigos por favor, use a tag code. Seu uso é bem simples:

Seu código

Primeiro de tudo, você pode explicar qual é a estrutura do seu genoma, e como você bolou o algoritmo de mutação e cruzamento? É você que quem que implementar o framework de AG? Por que se não for, talvez fosse uma boa você pegar um framework pronto, como o próprio SofiaIA:




Posso enviar os código para você da versão Java do Engine. E aí você só teria que se preocupar com a estrutura do genoma e seus métodos de mutação e cruza.

Por fim, vale lembrar que o uso da classe Vector não é recomendado desde o Java 1.2. No lugar, procure usar o ArrayList, através da interface List.
List lista = new ArrayList();

#3

Sobre ArrayList, dê uma olhada nesse tópico: http://www.guj.com.br/posts/list/74068.java#389435

#4

Vini tem como disponibilizar os fontes para Java? Uu achei bastante interessante o SofiaIA e mais elegante do que eu tinha montado para mim, rs

#5

Esse é o cacheiro viajante.

Dê uma lida aqui:

Solução com RNA
http://www.patol.com/java/TSP/index.html

Solução com AGs
http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html

#6

Tem sim, mas só tenho a parte do genético.

#7

[quote=ViniGodoy]Oi.

Sempre que postar códigos por favor, use a tag code. Seu uso é bem simples:

Seu código

Primeiro de tudo, você pode explicar qual é a estrutura do seu genoma, e como você bolou o algoritmo de mutação e cruzamento? É você que quem que implementar o framework de AG? Por que se não for, talvez fosse uma boa você pegar um framework pronto, como o próprio SofiaIA:




Posso enviar os código para você da versão Java do Engine. E aí você só teria que se preocupar com a estrutura do genoma e seus métodos de mutação e cruza.

Por fim, vale lembrar que o uso da classe Vector não é recomendado desde o Java 1.2. No lugar, procure usar o ArrayList, através da interface List.
List<String> lista = new ArrayList<String>();[/quote]

Vinny, obrigada por responder.
Quando comecei a pesquisar sobre o assunto, achei o SofiaIA bastante interessante, e até me animei.
Mas é exigência do problema que tudo seja construído por que está desenvolvendo o problema.
Como eu ainda não tenho muita experiência com Java, acabei não conseguindo fazer mais que isso.
Usei o vector porque encontrei muitos problemas com o ArrayList, e como eu precisava de uma solução em curto espaço de tempo, dei preferência a desenvolver com o que eu tinha certeza como usar. Pretendo, num futuro próximo, refinar o código.

Você perguntou sobre a mutação, e não sei se é isso que você quer saber: A minha rota é gerada com a seguinte estrutura: 1-2-3-4-1-5-6-7-1-8-9-10-1, sendo 1 minha cidade de origem. Quando o caminnhão chega no máximo da carga que ele pode transportar, eu volto pra 1. Pensei em usar o shuffle entre os 1, porque assim eu só teria que recalcular os custo, sem mexer com as demandas.

#8

[quote=Laurinha_RJ]Vinny, obrigada por responder. Quando comecei a pesquisar sobre o assunto, achei o SofiaIA bastante interessante, e até me animei.
Mas é exigência do problema que tudo seja construído por que está desenvolvendo o problema.[/quote]

Ok, nesse caso você terá que implementar tudo mesmo.

Que tipo de problemas? O uso do ArrayList é exatamente igual ao do Vector. Você não está confundindo com array primitivo?

Bom, as três perguntas que se deve fazer na hora de montar qualquer genético são:

  1. Como vou misturar a informação de dois genomas?
  2. Como vou alterar um único genoma, mantendo um indivíduo que faça sentido?
  3. Como vou avaliar um indivíduo?

Primeiro você responde essas 3, sem pensar no algoritmo. Depois disso, passar pro computador é fácil. É claro que para responde-las, você terá que pensar na estrutura do seu genoma.

#9

Por mim sem problema, gostaria de ver como ficou !

[]s

#10

Caro ViniGodoy, estou com um problema para codificação do seguinte problema, utilizando AG.

Encontrar o ponto máximo da função: f(x) = x2, com f(x) sujeita às seguintes restrições: 0 ≤ x ≤ 31 e x é inteiro

? Codificar x como vetor binário
? Criar uma população inicial com 4 indivíduos
? Aplicar Mutação com taxa de 1%
? Aplicar Crossover com taxa de 60%
? Usar seleção proporcional à aptidão (Roleta)
? Por simplicidade, a aptidão será a própria função objetivo.
? Usar 5 gerações.

Você tem algum código em relação ao desenvolvimento do caixeiro viajante?
Você tem alguma “luz” de como pode-se fazer isso de forma mais simples?
Att.

#11

Se você tivesse isso disponível ainda, iria ajudar bastante :slight_smile:

Aguardo contato. Att.

#12

Tenho sim, mas em C#.

Eis um exemplo. Para mais referências:
http://www.pontov.com.br/files/outros/vinigodoy/genetic.pdf

Quanto ao seu problema inicial, é bem fácil modelar com genético.
Com essa API que montei vc faz brincando.

Mas seria bom vc estudar e fazer sua própria implementação.
Não é difícil.

#13

Estou tentando fazer a parte da mutação do AG…

Tentei dessa forma, porém não estou obtendo êxito, alguém sabe como proceder?

Att.

[code]
public class Mutacao {

public String [] populacaoMutacao (String [] populacao){
	
	int posicaoQuebra = (int) (Math.random());  	
	String [] populacaoMutacao = new String [4];
	String filho;
	
		for (int i = 0; i < populacaoMutacao.length; i++) {
			double valorMutacao = (Math.random());;    	
	    	
			if (valorMutacao <= 1){
	    		
			if(populacao[i].charAt(posicaoQuebra) == 1){
            filho = populacao[i].replaceAll(populacao[i].substring(posicaoQuebra,posicaoQuebra+1), "0");
            populacaoMutacao[i] = filho;
        }
		else{
            filho = populacao[i].replaceAll(populacao[i].substring(posicaoQuebra, posicaoQuebra+1), "1");
            populacaoMutacao[i] = filho;
        }
		}
   	}
   return populacao;
}

}[/code]

Obrigado :slight_smile:

#14

Se seu genoma é binário, por que você está usando a classe String para representá-lo? Essa é uma péssima idéia, pois a classe é imutável.

Use no lugar a classe BitSet que, além de ser consideravelmente mais rápida e consumir muito menos memória, terá métodos bastante práticos como o flip(), que inverte o valor de um bit.

#15

[quote=ViniGodoy]Se seu genoma é binário, por que você está usando a classe String para representá-lo? Essa é uma péssima idéia, pois a classe é imutável.

Use no lugar a classe BitSet que, além de ser consideravelmente mais rápida e consumir muito menos memória, terá métodos bastante práticos como o flip(), que inverte o valor de um bit.[/quote]

Muito obrigado pela informação ViniGodoy! Vou tentar mudar aqui :slight_smile:

#16