Introdução aos Algoritmos Genéticos com Java
Os algoritmos genéticos são inspirados pela natureza e se baseiam na ideia da evolução. John Holland desenvolveu esse algoritmo pensando em como as espécies mudam e melhoram com o tempo. Ele pegou a ideia de Charles Darwin de que os mais fortes ou mais adequados sobrevivem e se adaptam melhor ao ambiente. No mundo da computação, isso significa encontrar a melhor solução para um problema.
Basicamente, esses algoritmos tentam resolver problemas testando várias soluções até achar a melhor. Assim como na natureza, as soluções que não são tão boas são descartadas, e as melhores são mantidas e melhoradas. O funcionamento desse algoritmo é mais fácil de entender com um fluxograma, que mostraremos a seguir.
Um algoritmo começa com um conjunto de soluções (representadas por indivíduos) chamado população. Soluções de uma população são tomadas e usadas para formar uma nova população, pois há uma chance de que a nova população seja melhor que a antiga.
Indivíduos que são escolhidos para formar novas soluções (descendentes) são selecionados de acordo com sua aptidão — quanto mais adequados forem, mais chances têm de se reproduzir.
As fases consideradas em um algoritmo genético são:
Inicialização: Crie uma população inicial de soluções potenciais (cromossomos). Cada cromossomo representa uma possível rota no problema do TSP (Problema do Caixeiro Viajante).
Avaliação: Avalie a aptidão de cada cromossomo. No contexto do TSP, a aptidão é a distância total da rota. Quanto menor a distância, mais apto é o cromossomo.
Seleção: Selecione um subconjunto de cromossomos para se tornarem pais com base em sua aptidão. Os cromossomos mais aptos têm maior probabilidade de serem selecionados.
Crossover: Realize o crossover (recombinação) nos pais selecionados para criar novos descendentes (filhos). Esta etapa ajuda a explorar novas soluções no espaço de solução.
Mutação: Aplique mutação em alguns dos descendentes com uma baixa probabilidade. A mutação introduz alterações aleatórias para manter a diversidade genética na população.
Substituição: Substitua a população antiga pela nova população de descendentes.
Término: Repita o processo por um número fixo de gerações ou até que um critério de término seja atingido (por exemplo, um número máximo de iterações).
Os algoritmos genéticos, com sua abordagem inspirada na natureza para resolver problemas, encontraram uma variedade de aplicações em muitos campos da vida real. Sua capacidade de buscar e otimizar soluções o torna uma ferramenta valiosa para várias áreas. Vamos explorar algumas das principais aplicações dos algoritmos genéticos em cenários do mundo real:
- Otimização de Projeto e Engenharia: Os algoritmos genéticos são frequentemente usados para otimizar designs de produtos, desde a aerodinâmica de carros até a eficiência de turbinas eólicas. Ao variar diferentes parâmetros e avaliar os resultados, os engenheiros podem encontrar designs que atendam a critérios específicos de forma eficaz.
- Programação e Logística: Empresas de transporte e logística utilizam algoritmos genéticos para otimizar rotas de entrega, minimizando os custos e o tempo de viagem. Similarmente, as companhias aéreas os usam para programar voos e tripulações, garantindo eficiência operacional.
- Biotecnologia e Farmacologia: Na busca por novas drogas e tratamentos, os algoritmos genéticos ajudam a identificar combinações de compostos que podem ser eficazes contra doenças específicas. Eles podem explorar um vasto espaço de possíveis soluções rapidamente, acelerando a pesquisa e a descoberta.
- Jogos e Simulações: Em jogos, esses algoritmos são usados para otimizar comportamentos de inteligência artificial, permitindo que NPCs (personagens não jogáveis) se adaptem e reajam de maneira mais realista aos jogadores.
- Mercado Financeiro: Na área financeira, os algoritmos genéticos são utilizados para otimizar estratégias de trading, buscando combinações de indicadores e parâmetros que possam maximizar os retornos de investimento.
- Reconhecimento de Padrões e Machine Learning: Eles também são empregados na seleção de características e na otimização de modelos, melhorando a eficácia dos sistemas de reconhecimento.
Estas são apenas algumas das muitas aplicações dos algoritmos genéticos. A verdadeira beleza dessa abordagem é sua adaptabilidade. Independentemente do domínio ou do problema específico, se há uma necessidade de otimização ou busca por soluções em um vasto espaço de possibilidades, os algoritmos genéticos podem oferecer uma abordagem poderosa e eficaz e ainda assim simples de executar e entender.
Implementando o Algoritmo Genético em Java
Passo 1: Representação de uma População (population)
Em algoritmos genéticos, a noção de “população” é essencial. Ela constitui um conjunto de soluções possíveis para um determinado problema. No contexto da competição na balança comercial entre países, cada “solução” (ou, em termos genéticos, cada “cromossomo”) pode representar um conjunto possível de decisões ou políticas comerciais que um país pode adotar. Assim, a população é uma coletânea destes cromossomos, ou neste caso, de países com seus respectivos atributos.
O código apresentado ilustra a criação de uma população em Java:
private ArrayList<Country> generatePopulation() {
ArrayList<Country> population = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < POPULATION_SIZE; i++) {
double[] gdpValues = {random.nextDouble() * 1000000000, random.nextDouble() * 1000000000}; // Produção para ambos os bens
population.add(new Country("Country " + i, gdpValues, random.nextInt(1000000))); // Supondo uma população aleatória
}
return population;
}Passo 2: Função de Aptidão (Fitness Function)
Uma vez que temos a representação da nossa população, o próximo passo no algoritmo genético é determinar o quão “adequada” ou “apta” cada solução é em relação ao problema em mãos. Esta avaliação é feita pela função de aptidão (ou “fitness function” em inglês). Essa função tem como objetivo atribuir uma pontuação a cada cromossomo, refletindo o quão bem ele se saiu no cenário proposto.
No contexto da competição na balança comercial entre países, a função de aptidão precisa avaliar o desempenho de um país (cromossomo) com base em várias métricas. Vamos observar o código fornecido:
int evaluate(String country, List<String> population) {
int index = population.indexOf(country);
int populationSize = COUNTRY_POPULATIONS[index];
int score = 0;
// Políticas
for (int i = 0; i < GENOTYPE_LENGTH; i++) {
if (country.charAt(i) == '1') {
score++;
}
}
// Consumo interno
score += populationSize / 1_000_000;
// Importação/exportação
for (int i = GENOTYPE_LENGTH; i < country.length(); i++) {
if (country.charAt(i) == '1') {
score++; // Benefício da exportação
String otherCountry = population.get(i - GENOTYPE_LENGTH);
if (otherCountry.charAt(i) == '1' && populationSize > COUNTRY_POPULATIONS[i - GENOTYPE_LENGTH]) {
score++; // Benefício da importação se a população for maior
}
}
}
return score;
}Passo 3: Seleção (Selection)
Após representar nossa população e avaliar o desempenho de cada país por meio da função de aptidão, o próximo passo no algoritmo genético é a seleção. A ideia por trás da seleção é escolher cromossomos da população atual para serem os “pais” das próximas gerações. A seleção é fundamental, pois garante que os cromossomos com melhor desempenho (ou maior aptidão) têm uma chance maior de passar seus genes (ou atributos) para as próximas gerações.
No cenário da competição na balança comercial entre países, queremos selecionar aqueles países que têm políticas e relações comerciais mais vantajosas. Estes serão os “pais” que ajudarão a formar a próxima geração de soluções, combinando e possivelmente melhorando as características atuais.
Vamos examinar o código fornecido:
List<String> selectParent(List<String> population) {
List<String> selectedParents = new ArrayList<>();
int totalFitness = population.stream().mapToInt(country -> evaluate(country, population)).sum();
for (int i = 0; i < POPULATION_SIZE * SELECTION_RATE; i++) {
double randomValue = Math.random() * totalFitness;
double cumulativeFitness = 0;
for (String country : population) {
cumulativeFitness += evaluate(country, population);
if (cumulativeFitness > randomValue) {
selectedParents.add(country);
break;
}
}
}
return selectedParents;
}Passo 4: Crossover (Recombinação)
Depois de representar nossa população, avaliar cada solução por meio da função de aptidão e selecionar os “pais” adequados, chegamos ao próximo passo crucial do algoritmo genético: o crossover, também conhecido como recombinação. O objetivo do crossover é gerar novos cromossomos, combinando as características dos pais selecionados. Essa combinação é esperada para produzir uma nova geração que herde as melhores características de ambos os pais, aproximando-se de soluções ainda melhores.
No contexto da competição na balança comercial entre países, o crossover representa a combinação de políticas e estratégias comerciais de dois países, na esperança de criar um novo conjunto de políticas que seja mais eficaz em promover um balanço comercial positivo.
Analisemos o código fornecido:
String crossover(String parent1, String parent2) {
StringBuilder child = new StringBuilder();
for (int i = 0; i < GENOTYPE_LENGTH; i++) {
if (Math.random() > 0.5) {
child.append(parent1.charAt(i));
} else {
child.append(parent2.charAt(i));
}
}
return child.toString();
}Neste método de crossover, estamos usando uma abordagem chamada de crossover uniforme. Para cada posição no cromossomo, o algoritmo decide aleatoriamente de qual dos pais a informação (o gene) será herdada. Esse processo resulta em um “filho” que é uma mistura dos genes de ambos os pais.
O crossover é uma das operações mais importantes em algoritmos genéticos, pois permite a exploração de novas soluções no espaço de busca, combinando os melhores traços das gerações anteriores. Junto com a mutação, que será discutida no próximo passo, essas operações são fundamentais para garantir a diversidade genética e convergir para soluções ótimas ou subótimas.
Passo 5: Mutação (Mutation)
Após representar nossa população, avaliar as soluções, selecionar pais adequados e realizar o crossover para gerar novos cromossomos, entramos no passo de mutação no algoritmo genético. A mutação é um processo que introduz pequenas alterações aleatórias em um cromossomo. Seu principal objetivo é adicionar diversidade genética à população e evitar que o algoritmo fique preso em mínimos locais, isto é, soluções que são boas localmente mas não são as melhores globalmente.
No contexto da competição na balança comercial entre países, a mutação pode ser interpretada como uma mudança súbita e inesperada na política ou estratégia comercial de um país. Estas mudanças, embora pequenas, podem ter um impacto significativo nas relações comerciais e no desempenho do país.
Vejamos o código fornecido:
String mutate(String country) {
StringBuilder mutated = new StringBuilder();
for (int i = 0; i < country.length(); i++) {
if (Math.random() < MUTATION_RATE) {
mutated.append(country.charAt(i) == '1' ? '0' : '1');
} else {
mutated.append(country.charAt(i));
}
}
return mutated.toString();
}Passo 6 Encerramento (Termination):
Tendo percorrido os processos de representação da população, avaliação das soluções, seleção, crossover e mutação, chegamos ao passo final, o encerramento. Este passo determina quando o algoritmo genético deve parar de procurar por soluções melhores. A decisão de encerrar pode ser baseada em vários critérios, tais como: atingir um número máximo de gerações, encontrar uma solução que atenda a um critério de adequação desejado, ou a ausência de melhoria significativa nas soluções por um determinado número de gerações.
Então, neste exemplo, o algoritmo genético termina após 10000 gerações, independentemente do estado ou da qualidade da população.
Em aplicações práticas de algoritmos genéticos, existem vários critérios de terminação que podem ser usados:
- Número fixo de gerações: como no exemplo.
- Convergência: o algoritmo pode ser encerrado se a população convergir para uma solução (por exemplo, se todos ou uma grande parte dos indivíduos na população forem idênticos ou muito semelhantes).
- Estabilidade da fitness: se a melhor (ou média) aptidão (fitness) na população não melhorar significativamente por um determinado número de gerações, o algoritmo pode ser interrompido.
- Tempo: em algumas aplicações, você pode simplesmente querer executar o algoritmo por um determinado período de tempo.
- Objetivo alcançado: o algoritmo pode ser interrompido se um indivíduo na população atingir um certo nível de aptidão ou resolver o problema exatamente.
Vejamos o código:
for (int generation = 0; generation < 10000; generation++) {
List<String> newPopulation = new ArrayList<>();
for (int i = 0; i < POPULATION_SIZE; i++) {
String parent1 = selectParent(population);
String parent2 = selectParent(population);
String child = crossover(parent1, parent2);
child = mutate(child);
newPopulation.add(child);
}
population = newPopulation;
String bestCountry = getBest(population);
String worstCountry = getWorst(population);
////Codigo completo
import java.util.*;
public class GeneticAlgorithm1 {
static final int POPULATION_SIZE = 10;
static final int POLICY_LENGTH = 10;
static final double SELECTION_RATE = 0.5;
static final int GENOTYPE_LENGTH = 20; // 10 para políticas e 10 para relações de comércio.
static final double MUTATION_RATE = 0.01;
static final int[] COUNTRY_POPULATIONS = new int[POPULATION_SIZE];
public static void main(String[] args) {
initializePopulations();
List<String> population = generateInitialPopulation();
for (int generation = 0; generation < 100; generation++) {
List<String> newPopulation = new ArrayList<>();
List<String> parents = selectParent(population);
for (int i = 0; i < POPULATION_SIZE; i++) {
String parent1 = parents.get(new Random().nextInt(parents.size()));
String parent2 = parents.get(new Random().nextInt(parents.size()));
String child = crossover(parent1, parent2);
child = mutate(child);
newPopulation.add(child);
}
population = newPopulation;
String bestCountry = getBest(population);
String worstCountry = getWorst(population);
System.out.println("Generation: " + generation);
System.out.println("Best Country: " + bestCountry + " PIB: " + evaluate(bestCountry, population));
System.out.println("Worst Country: " + worstCountry + " PIB: " + evaluate(worstCountry, population));
printTradeMatrix(population);
System.out.println("-------------------------------");
}
}
static void initializePopulations() {
for (int i = 0; i < POPULATION_SIZE; i++) {
COUNTRY_POPULATIONS[i] = 1_000_000 + (int)(Math.random() * 9_000_000);
}
}
static List<String> generateInitialPopulation() {
List<String> population = new ArrayList<>();
for (int i = 0; i < POPULATION_SIZE; i++) {
StringBuilder genotype = new StringBuilder();
for (int j = 0; j < GENOTYPE_LENGTH; j++) {
genotype.append(Math.random() > 0.5 ? "1" : "0");
}
population.add(genotype.toString());
}
return population;
}
static List<String> selectParent(List<String> population) {
List<String> selectedParents = new ArrayList<>();
int totalFitness = population.stream().mapToInt(country -> evaluate(country, population)).sum();
for (int i = 0; i < POPULATION_SIZE * SELECTION_RATE; i++) {
double randomValue = Math.random() * totalFitness;
double cumulativeFitness = 0;
for (String country : population) {
cumulativeFitness += evaluate(country, population);
if (cumulativeFitness > randomValue) {
selectedParents.add(country);
break;
}
}
}
return selectedParents;
}
static String crossover(String parent1, String parent2) {
StringBuilder child = new StringBuilder();
for (int i = 0; i < GENOTYPE_LENGTH; i++) {
if (Math.random() > 0.5) {
child.append(parent1.charAt(i));
} else {
child.append(parent2.charAt(i));
}
}
return child.toString();
}
static String mutate(String country) {
StringBuilder mutated = new StringBuilder();
for (int i = 0; i < country.length(); i++) {
if (Math.random() < MUTATION_RATE) {
mutated.append(country.charAt(i) == '1' ? '0' : '1');
} else {
mutated.append(country.charAt(i));
}
}
return mutated.toString();
}
static int evaluate(String country, List<String> population) {
int index = population.indexOf(country);
int populationSize = COUNTRY_POPULATIONS[index];
int score = 0;
// Políticas
for (int i = 0; i < GENOTYPE_LENGTH; i++) {
if (country.charAt(i) == '1') {
score++;
}
}
// Consumo interno
score += populationSize / 1_000_000;
// Importação/exportação
for (int i = GENOTYPE_LENGTH; i < country.length(); i++) {
if (country.charAt(i) == '1') {
score++; // exportação
String otherCountry = population.get(i - GENOTYPE_LENGTH);
if (otherCountry.charAt(i) == '1' && populationSize > COUNTRY_POPULATIONS[i - GENOTYPE_LENGTH]) {
score++; // importação se a população for maior
}
}
}
return score;
}
static String getBest(List<String> population) {
return population.stream().max(Comparator.comparingInt(country -> evaluate(country, population))).orElseThrow();
}
static String getWorst(List<String> population) {
return population.stream().min(Comparator.comparingInt(country -> evaluate(country, population))).orElseThrow();
}
static void printTradeMatrix(List<String> population) {
System.out.println("\nTrade Matrix (Import/Export):");
for (String country : population) {
for (int i = POLICY_LENGTH; i < GENOTYPE_LENGTH; i++) {
System.out.print(country.charAt(i));
}
System.out.println();
}
}
}Conclusão
Neste artigo, utilizamos o Algoritmo Genético em Java como uma ferramenta ilustrativa para abordar um problema teórico no contexto do comércio entre países. É importante lembrar que o objetivo aqui não era fornecer uma solução real ou prática para desafios comerciais internacionais, mas sim destacar a capacidade a forma do algoritmo em lidar com questões de otimização.
Para um entendimento mais profundo e aplicado das dinâmicas econômicas globais, estamos desenvolvendo um simulador abrangente de economia, o “Global Economy”. Este simulador buscará incorporar as variáveis e complexidades intrínsecas às relações comerciais globais, assim como as relações economicas internas, proporcionando insights mais alinhados com cenários reais.
Em resumo, os algoritmos genéticos, com sua capacidade adaptativa, são ferramentas valiosas para ilustrar conceitos e abordagens. Ao mesmo tempo, quando se trata de questões práticas e profundamente entrelaçadas como o comércio internacional, ferramentas mais sofisticadas e abrangentes, como o simulador “Global Economy”, serão necessárias para uma análise verdadeiramente informada e holística.
