Genéticos: Exemplo em Java

Afluentes: Inteligência Artificial, Modelos Evolutivos e Tratamento de Incertezas

  1/*****************************************************************************
  2
  3Copyright 2001-2003 Saulo Popov Zambiasi. All rights reserved.
  4Last modified: 2004/06/03 23:04:00
  5
  6Genetico
  7   Programa para calcular uma configuracao ideal de gastos de
  8   uma residencia, utilizando algoritmos geneticos. As informacoes
  9   utilizadas sao ficticias.
 10
 11USO:
 12   java Genetico >> log.txt
 13
 14 ******************************************************************************/
 15
 16import java.util.*;
 17
 18public class Genetico {
 19	List<Elemento> populacao = new ArrayList<Elemento>();
 20	List<Integer> selecionados = new ArrayList<Integer>();
 21	private Random r = new Random();
 22	final double ideal = 45.0; // Preco ideal em reais
 23	final int POPULACAO = 50; // Populacao maxima
 24	final int SELECAO = 20; // Quantidade que pode exceder, nos cruzamentos.
 25	static final int EPOCAS = 100;
 26	static final int MUTANTES = 20;
 27	static final boolean MELHORES = true;
 28	static final boolean PIORES = false;
 29	static boolean DEBUG = true;
 30
 31	public void criaPopulacao() {
 32		for (int i = 0; i < POPULACAO; i++) {
 33			populacao.add(new Elemento());
 34		}
 35	}
 36
 37	public void ordenaPopulacao() {
 38		recalculaPontuacao();
 39		for (int a = 0; a < populacao.size() - 1; a++) {
 40			for (int b = a + 1; b > 0; b--) {
 41				Elemento e1 = (Elemento) populacao.get(b - 1);
 42				Elemento e2 = (Elemento) populacao.get(b);
 43				double v1 = e1.pontuacao - ideal;
 44				double v2 = e2.pontuacao - ideal;
 45				if (v1 < 0) {
 46					// Calcula o modulo
 47					v1 *= -1;
 48				}
 49				if (v2 < 0) {
 50					// Calcula o modulo
 51					v2 *= -1;
 52				}
 53				// Inverte
 54				if (v1 < v2) {
 55					populacao.remove(b - 1);
 56					populacao.remove(b - 1);
 57					populacao.add(b - 1, e2);
 58					populacao.add(b, e1);
 59				}
 60			}
 61		}
 62	}
 63
 64	// os elementos selecionados podem ser os mais fortes ou os mais fracos
 65	void selecao(int quantidade, boolean fortes) {
 66		selecionados.clear();
 67		ordenaPopulacao();
 68		// Criando a roleta
 69		Vector<Integer> roleta = new Vector<Integer>();
 70		int peso = 1;
 71		if (!fortes) {
 72			peso = 10;
 73		}
 74		int cont = 0;
 75		for (int i = 0; i < populacao.size(); i++) {
 76			for (int j = 0; j < peso; j++) {
 77				Integer aux = i;
 78				roleta.add(aux);
 79			}
 80			if (cont > 4) {
 81				if (fortes) {
 82					peso++;
 83				} else {
 84					peso--;
 85				}
 86				cont = 0;
 87			} else {
 88				cont++;
 89			}
 90		}
 91		// Seleciona os elementos na roleta;
 92		for (int i = 0; i < SELECAO; i++) {
 93			// pega um numero aleatorio na roleta
 94			int escolhido = r.nextInt(roleta.size());
 95			// pega o indice na roleta
 96			Integer aux = (Integer) roleta.get(escolhido);
 97			// pega o elemento com seu indice
 98			Elemento e = (Elemento) populacao.get(aux.intValue());
 99
100			if (!e.selecionado) {
101				// seta o elemento como selecionado
102				e.selecionado = true;
103				// insere seu indice no vetor de selecionados
104				selecionados.add(aux);
105			} else {
106				i--;
107			}
108		}
109		dbgln("Selecionados = " + selecionados.size());
110	}
111
112	void cruzamento() {
113		while (selecionados.size() > 0) {
114			// Pega o primeiro elemento da lista de selecionados
115			Integer aux1 = (Integer) selecionados.get(0);
116			Elemento e1 = (Elemento) populacao.get(aux1.intValue());
117			e1.selecionado = false;
118			selecionados.remove(0);
119
120			// Pega o segundo elemento da lista de selecionados
121			Integer aux2 = (Integer) selecionados.get(0);
122			Elemento e2 = (Elemento) populacao.get(aux2.intValue());
123			e2.selecionado = false;
124			selecionados.remove(0);
125
126			// cruza, criando dois filhos com as informacoes trocadas e
127			// insere-os na populacao
128			Elemento f1 = new Elemento(e1);
129			Elemento f2 = new Elemento(e2);
130			int idx1 = r.nextInt(5);
131			int idx2 = r.nextInt(5);
132			int troca = f1.elemento[idx1];
133			f1.elemento[idx1] = f2.elemento[idx1];
134			f2.elemento[idx1] = troca;
135			if (idx1 != idx2) {
136				troca = f1.elemento[idx2];
137				f1.elemento[idx2] = f2.elemento[idx2];
138				f2.elemento[idx2] = troca;
139			}
140			populacao.add(f1);
141			populacao.add(f2);
142			dbg("Cruzando os elementos " + idx1 + " e " + idx2);
143			dbg(" dos individuos " + aux1.intValue());
144			dbgln(" e " + aux2.intValue() + "---------------");
145			e1.mostrarInformacoes();
146			e2.mostrarInformacoes();
147			f1.calculaPontuacao();
148			f1.mostrarInformacoes();
149			f2.calculaPontuacao();
150			f2.mostrarInformacoes();
151		}
152		ordenaPopulacao();
153	}
154
155	void mutacao() {
156		// Pode mutar ate 4 elementos
157		int qtd = r.nextInt(MUTANTES + 1);
158		for (int i = qtd; i > 0; i--) {
159			// Escolhe um elemento aleatoriamente
160			int j = r.nextInt(populacao.size());
161			Elemento e = (Elemento) populacao.get(i);
162			// Escolhe aleatoriamente um de seus elementos
163			int k = r.nextInt(5);
164			dbgln("Mutando elemento " + k + " do individulo " + j);
165			if (DEBUG) {
166				e.mostrarInformacoes();
167			}
168			// Muda sua informacao aleatoriamente
169			e.elemento[k] = r.nextInt(10) + 1;
170			e.calculaPontuacao();
171			if (DEBUG) {
172				e.mostrarInformacoes();
173			}
174		}
175		ordenaPopulacao();
176	}
177
178	void matar() {
179		boolean matando = true;
180		int i = 0;
181		while (matando) {
182			Elemento e = (Elemento) populacao.get(i);
183			if (e.selecionado) {
184				populacao.remove(i);
185				i--;
186			}
187			i++;
188			if (i >= populacao.size()) {
189				matando = false;
190			}
191		}
192		selecionados.clear();
193	}
194
195	void recalculaPontuacao() {
196		for (int i = 0; i < populacao.size(); i++) {
197			Elemento e = (Elemento) populacao.get(i);
198			e.calculaPontuacao();
199		}
200	}
201
202	void mostrarResultado() {
203		System.out.println("\n\nResultado do algoritmo");
204		for (int i = 0; i < POPULACAO; i++) {
205			Elemento e = (Elemento) populacao.get(populacao.size() - 1 - i);
206			System.out.print("" + (i + 1) + "o: ");
207			e.mostrarInformacoes();
208		}
209	}
210
211	public static void dbg(String s) {
212		if (DEBUG) {
213			System.out.print(s);
214		}
215	}
216
217	public static void dbgln(String s) {
218		if (DEBUG)
219			System.out.println(s);
220	}
221
222	public static void main(String[] arguments) {
223		Genetico g = new Genetico();
224		dbgln("Criando Populacao");
225		g.criaPopulacao();
226		for (int i = 0; i < EPOCAS; i++) {
227			dbgln("**** EPOCA " + (i + 1) + " ****");
228			dbgln("Populacao = " + g.populacao.size());
229			dbgln("Selecionando os 20 melhores");
230			g.selecao(20, MELHORES);
231			dbgln("Cruzamento");
232			g.cruzamento();
233			dbgln("Populacao = " + g.populacao.size());
234			dbgln("Selecionando os 20 piores");
235			g.selecao(20, PIORES);
236			dbgln("Matando");
237			g.matar();
238			dbgln("Populacao = " + g.populacao.size());
239			dbgln("Mutacao");
240			g.mutacao();
241		}
242		g.mostrarResultado();
243	}
244}
245
246/**************************************************************
247 * Caracteristicas dos elementos (total * 30dias) 0 - Lampadas - 11-20h/dia a
248 * 100w/h - 1-2k/dia 1 - Chuveiro - 0.1-0.6h/dia a 5kw/h - 0.25-2.75k/dia 2 -
249 * Televisao - 1-10h/dia a 100w/h - 0-1k/dia 3 - Computador - 1-10h/dia a 300w/h
250 * - 0-3k/dia 4 - Video K7 - 1-6h/dia a 50w/h - 0-0.5k/dia
251 **************************************************************/
252
253class Elemento {
254	int[] elemento = new int[5];
255	double pontuacao = 0;
256	boolean selecionado = false;
257	final double kwh = 0.38;
258	static Random r = new Random();
259
260	Elemento() {
261		for (int i = 0; i < 5; i++) {
262			elemento[i] = r.nextInt(10) + 1;
263		}
264		calculaPontuacao();
265		selecionado = false;
266		if (Genetico.DEBUG) {
267			mostrarInformacoes();
268		}
269	}
270
271	Elemento(Elemento e) {
272		for (int i = 0; i < 5; i++) {
273			elemento[i] = e.elemento[i];
274		}
275		selecionado = false;
276	}
277
278	void mostrarInformacoes() {
279		System.out.print("LAMPADAS: [" + (int) (elemento[0] + 9) + "h] ");
280		System.out.print("CHUVEIRO: [" + (int) (((elemento[1] / 2) + 1) * 6)
281				+ "min] ");
282		System.out.print("TELEVISAO: [" + (int) (elemento[2]) + "h] ");
283		System.out.print("COMPUTADOR: [" + (int) (elemento[3]) + "h] ");
284		System.out.print("VIDEO K7: [" + (int) (elemento[4] / 2) + "h] ");
285		System.out.println("VALOR: R$ (" + (int) pontuacao + ",00)");
286	}
287
288	public void calculaPontuacao() {
289		pontuacao = (elemento[0] + 10) * 100; // Lampadas
290		pontuacao += ((elemento[1] + 2) / 2) * 500; // Chuveiro
291		pontuacao += elemento[2] * 100; // Televisao
292		pontuacao += elemento[3] * 300; // Computador
293		pontuacao += ((elemento[4] + 2) / 2) * 50; // Video k7
294		pontuacao *= 30; // em 30 Dias
295		pontuacao = (pontuacao / 1000) * kwh; // kwh = 0.38 - Valor em reais
296	}
297}