Otimização de recifes de coral — Coral Reefs Optimization (CRO)
122
0
Conteúdo
Introdução
Algoritmos bioinspirados, que se inspiram em processos e sistemas naturais, têm despertado grande interesse entre desenvolvedores recentemente. Entre eles, destaca-se o Algoritmo de Otimização de Recifes de Coral (Coral Reef Optimization, CRO), proposto originalmente por S. Salcedo-Sanz e colaboradores em 2014.
O algoritmo CRO é baseado na modelagem dos processos de formação e desenvolvimento de recifes de coral na natureza. Esses processos incluem diversos mecanismos de reprodução dos corais (reprodução sexual externa e interna, além da assexuada), competição por espaço limitado no recife e eliminação de indivíduos fracos. Assim como a evolução forma recifes de coral estáveis e adaptados na natureza, o algoritmo CRO permite explorar o espaço de busca e encontrar soluções ótimas ou próximas do ótimo para diferentes tarefas.
Neste trabalho será apresentada uma versão aprimorada do algoritmo CROm com um mecanismo modificado de eliminação, baseado no uso de uma distribuição de potência inversa para gerar novas soluções nas vizinhanças das melhores. A abordagem proposta não apenas preserva as vantagens tradicionais do CRO, como capacidade exploratória, equilíbrio natural entre diversificação e intensificação do espaço de busca, mas também adiciona um mecanismo mais eficiente, que permite localizar com maior precisão áreas promissoras e convergir mais rapidamente para soluções ótimas.
Será apresentado um teste abrangente do algoritmo proposto em um conjunto de funções clássicas de teste de otimização, demonstrando sua melhor eficiência em comparação ao algoritmo CRO original e a outras meta-heurísticas modernas. Os resultados dos experimentos mostram que a abordagem proposta é especialmente eficaz para tarefas com funções objetivo multimodais e estrutura complexa do espaço de busca.
O artigo está estruturado da seguinte forma: primeiro analisamos os conceitos básicos e os princípios de funcionamento do algoritmo CRO padrão, depois descrevemos detalhadamente as modificações propostas e sua fundamentação teórica. Em seguida, vem a avaliação experimental do algoritmo e a análise dos resultados. Nas considerações finais discutimos os resultados obtidos, as limitações do método proposto e possíveis direções para pesquisas futuras.
Implementação do algoritmo
A ideia principal do CRO consiste em modelar colônias de corais que se desenvolvem e competem por espaço no recife, formando no final uma estrutura otimizada. Cada coral no recife representa uma solução potencial para o problema de otimização analisado.
O recife é modelado como uma grade bidimensional de tamanho N×M. Cada célula da grade pode estar ocupada por um coral ou permanecer vazia. O coral representa uma solução codificada do problema de otimização. Para cada coral é definida uma função de adaptabilidade (saúde), que corresponde à função objetivo da tarefa de otimização.
O parâmetro ρ₀ ∈ (0,1) determina a fração inicial de preenchimento do recife por corais, isto é, a relação entre o número de células ocupadas e o número total de células no início do algoritmo. A inicialização do recife é realizada da seguinte forma:
- Define-se o tamanho do recife N×M e a fração inicial de preenchimento ρ₀.
- Selecionam-se aleatoriamente ⌊ρ₀ × N × M⌋ células do recife para posicionamento dos corais iniciais.
- Os corais iniciais são gerados aleatoriamente dentro da área de busca e colocados nas células selecionadas.
Após a inicialização do recife, inicia-se o processo iterativo de formação e desenvolvimento do recife, composto por várias etapas:
Reprodução sexual externa (Broadcast Spawning). Para esse tipo de reprodução é escolhida uma determinada fração Fₑ dos corais existentes. Os corais selecionados formam pares e, usando operadores de cruzamento, geram descendentes. Cada par produz uma larva utilizando um operador de cruzamento (normalmente uma média).
Reprodução sexual interna (Brooding). A fração restante dos corais (1-Fₑ) participa do processo de reprodução interna, em que cada coral produz descendentes por mutação. Para cada coral selecionado para reprodução interna, a larva é criada com um operador de mutação e geralmente representa uma pequena alteração aleatória da solução codificada. Fixação das larvas. Após a formação das larvas nas etapas de reprodução, cada uma tenta ocupar um espaço no recife. O processo de fixação é realizado segundo as seguintes regras:
- A larva escolhe aleatoriamente uma célula (i, j) no recife.
- Se a célula estiver livre, a larva a ocupa.
- Se a célula estiver ocupada, a larva pode expulsar o coral existente apenas se sua adaptabilidade for maior: f(larva) > f(Ξᵢⱼ).
- Se a expulsão não ocorrer, a larva pode tentar fixar-se em outro lugar (até o número máximo de tentativas k).
- Se após k tentativas a larva não conseguir encontrar um lugar, ela morre.
Reprodução assexuada (Budding). Os melhores corais do recife (fração Fₐ) podem reproduzir-se de forma assexuada, criando cópias exatas de si mesmos (clones). Formalmente:
- Os corais são ordenados pelo valor da função de adaptabilidade.
- Os melhores Fₐ × 100% dos corais são selecionados para a reprodução assexuada.
- Cada coral selecionado cria um clone, que tenta fixar-se no recife seguindo as mesmas regras utilizadas no processo de fixação das larvas.
Extinção. Ao final de cada iteração, os piores corais do recife podem morrer com probabilidade Pd, liberando espaço para novos corais nas iterações seguintes.
O processo de formação do recife se repete até que o critério de parada seja cumprido, alcançando o número máximo de iterações. Após a parada, o melhor coral do recife representa a solução encontrada para o problema de otimização.
Figura 1. Esquema do funcionamento do algoritmo CRO
Na ilustração acima estão representadas as seis etapas principais do funcionamento do algoritmo:
- Inicialização (ρ₀ = 0.6) mostra a grade bidimensional (recife) parcialmente preenchida por corais coloridos, representando diferentes soluções.
- Reprodução externa (Fb = 0.9) mostra corais formando pares e criando larvas por meio de cruzamento.
- Reprodução interna (1-Fb = 0.1) mostra corais individuais produzindo larvas por mutação.
- Fixação das larvas (k = 3 tentativas) ilustra o processo de busca das larvas por um lugar no recife, incluindo tentativas bem-sucedidas e malsucedidas.
- Reprodução assexuada (Fa = 0.1) mostra os melhores corais (marcados com estrelas) criando cópias exatas de si mesmos.
- Extinção (Fd = 0.1, Pd = 0.05) mostra a remoção dos piores corais do recife.
Entrada: Parâmetros do recife (N, M, ρ₀, Fₑ, Fₐ, Fd, Pd, k)
Saída: Melhor solução encontrada
1. Inicialização:
- Criar um recife de tamanho N×M
- Preencher ⌊ρ₀ × N × M⌋ células com corais aleatórios
- Calcular a adaptabilidade de cada coral
2. Enquanto o critério de parada não for atendido:
3. Reprodução sexual externa:
- Selecionar a fração Fₑ dos corais para participar
- Formar pares e criar larvas por cruzamento
4. Reprodução sexual interna:
- Para os corais restantes (1-Fₑ), criar larvas por mutação
5. Fixação das larvas:
- Para cada larva:
- Tentar ocupar uma célula aleatória do recife
- Se estiver ocupada, expulsar o coral existente se tiver adaptabilidade maior
- Se não conseguir, tentar novamente (até k tentativas)
6. Reprodução assexuada:
- Ordenar os corais por adaptabilidade
- Os melhores Fₐ corais criam clones
- Os clones tentam fixar-se no recife
7. Extinção:
- Com probabilidade Pd executar a eliminação
- Remover a fração Fd dos piores corais
8. Retornar o melhor coral no recife
Agora podemos montar o código do algoritmo CRO. Vamos escrever a classe "C_AO_CRO", que implementa o algoritmo CRO e herda da classe base "C_AO".
Parâmetros do CRO:
Na classe são declarados parâmetros que controlam o comportamento do algoritmo:
- popSize: tamanho da população de corais.
- reefRows: altura do recife (quantidade de linhas na grade).
- reefCols: largura do recife (quantidade de colunas na grade).
- rho0: ocupação inicial do recife. É a porcentagem de células do recife ocupadas por corais no início do algoritmo.
- Fb: fração de corais que participam da reprodução externa (Broadcast Spawning).
- Fa: fração de corais que participam da reprodução assexuada (fragmentation).
- Fd: fração de corais a serem removidos devido à baixa adaptabilidade.
- Pd: probabilidade de eliminação de corais.
- attemptsNum: quantidade de tentativas que a larva faz para fixar-se no recife.
Métodos da classe:
- SetParams (): o método define os valores dos parâmetros do algoritmo, com base nos valores armazenados no array "params". Esse array permite alterar dinamicamente os parâmetros do algoritmo durante a execução.
- Init (): método de inicialização, recebe os intervalos de busca das variáveis de otimização (rangeMinP, rangeMaxP, rangeStepP) e a quantidade de épocas (epochsP). O método "Init" executa os preparativos necessários para o início do trabalho do algoritmo, como a inicialização da população e do recife.
- Moving (): função que implementa a lógica principal de movimentação dos corais no recife.
- Revision (): método responsável pela revisão e correção das posições dos corais no recife.
- InitReef (): inicializa a estrutura do recife, preparando-o para ser povoado por corais.
- LarvaSettling (): determina onde a larva do coral vai se fixar no recife, modela o processo de povoamento do recife por novos corais. O parâmetro "larva" representa a larva do coral.
- BroadcastSpawning (): processo de reprodução externa, quando os corais liberam larvas na água.
- Brooding (): processo alternativo de reprodução, quando as larvas se desenvolvem dentro do coral.
- AsexualReproduction (): processo de reprodução assexuada, quando os corais se fragmentam e formam novas colônias.
- Depredation (): processo de extinção, quando os corais são eliminados.
- GetReefCoordIndex (): converte as coordenadas do recife (linha e coluna) em um índice em um array unidimensional.
- SortAgentsByFitness (): ordena os corais de acordo com sua adaptabilidade (fitness).
Variáveis privadas:
- totalReefSize: tamanho total do recife (o produto de "reefRows" e "reefCols").
- occupied []: array de valores booleanos indicando se cada célula do recife está ocupada por um coral.
- reefIndices []: array de índices contendo os índices dos corais (do array "a []" da classe base "C_AO") nas células ocupadas do recife.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CRO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CRO () { } C_AO_CRO () { ao_name = "CRO"; ao_desc = "Coral Reef Optimization"; ao_link = "https://www.mql5.com/ru/articles/17760"; popSize = 50; // размер популяции reefRows = 20; // высота рифа reefCols = 20; // ширина рифа rho0 = 0.2; // начальная занятость рифа Fb = 0.99; // доля кораллов для внешнего размножения Fa = 0.01; // доля кораллов для бесполого размножения Fd = 0.8; // доля кораллов для удаления Pd = 0.9; // вероятность уничтожения attemptsNum = 20; // количество попыток для оседания личинок ArrayResize (params, 9); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "reefRows"; params [1].val = reefRows; params [2].name = "reefCols"; params [2].val = reefCols; params [3].name = "rho0"; params [3].val = rho0; params [4].name = "Fb"; params [4].val = Fb; params [5].name = "Fa"; params [5].val = Fa; params [6].name = "Fd"; params [6].val = Fd; params [7].name = "Pd"; params [7].val = Pd; params [8].name = "attemptsNum"; params [8].val = attemptsNum; } void SetParams () { popSize = (int)params [0].val; reefRows = (int)params [1].val; reefCols = (int)params [2].val; rho0 = params [3].val; Fb = params [4].val; Fa = params [5].val; Fd = params [6].val; Pd = params [7].val; attemptsNum = (int)params [8].val; } bool Init (const double &rangeMinP [], // минимальный диапазон поиска const double &rangeMaxP [], // максимальный диапазон поиска const double &rangeStepP [], // шаг поиска const int epochsP = 0); // количество эпох void Moving (); void Revision (); //---------------------------------------------------------------------------- int reefRows; // высота рифа int reefCols; // ширина рифа double rho0; // начальная занятость рифа double Fb; // доля кораллов для внешнего размножения double Fa; // доля кораллов для бесполого размножения double Fd; // доля кораллов для удаления double Pd; // вероятность уничтожения int attemptsNum; // количество попыток для оседания личинок private: //------------------------------------------------------------------- int totalReefSize; // общий размер рифа bool occupied []; // флаги занятости клеток рифа int reefIndices []; // индексы агентов в a[], соответствующие занятым клеткам // Вспомогательные методы void InitReef (); int LarvaSettling (S_AO_Agent &larva); void BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount); void Brooding (S_AO_Agent &larvae [], int &larvaCount); void AsexualReproduction (); void Depredation (); int GetReefCoordIndex (int row, int col); void SortAgentsByFitness (int &indices [], int &count); }; //——————————————————————————————————————————————————————————————————————————————
O método "Init" inicializa o algoritmo CRO: chama "StandardInit" da classe base, depois calcula o tamanho total do recife "totalReefSize", determina a quantidade inicial de corais "initialPopSize", inicializa os arrays "occupied" (ocupação das células) e "reefIndices" (índices dos corais), chama "InitReef ()" para posicionar os corais no recife e, por fim, retorna "true" em caso de sucesso.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CRO::Init (const double &rangeMinP [], // минимальный диапазон поиска const double &rangeMaxP [], // максимальный диапазон поиска const double &rangeStepP [], // шаг поиска const int epochsP = 0) // количество эпох { // Стандартная инициализация родительского класса if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Рассчитываем общий размер рифа totalReefSize = reefRows * reefCols; // Количество начальных кораллов не должно превышать popSize int initialPopSize = (int)MathRound (rho0 * totalReefSize); if (initialPopSize > popSize) initialPopSize = popSize; // Инициализация массива занятости и индексов ArrayResize (occupied, totalReefSize); ArrayResize (reefIndices, totalReefSize); // Заполняем массивы начальными значениями for (int i = 0; i < totalReefSize; i++) { occupied [i] = false; reefIndices [i] = -1; } // Инициализация рифа InitReef (); return true; } //——————————————————————————————————————————————————————————————————————————————O método "InitReef ()" da classe "C_AO_CRO" inicializa a população inicial de corais no recife. Primeiro é calculada a quantidade de corais para a inicialização, com base na densidade definida (rho0) do recife; essa quantidade é limitada pelo tamanho da população "popSize". Em seguida, para cada coral é selecionada uma posição aleatória, porém livre, no recife; após encontrá-la, ela é marcada como ocupada e o coral é associado a essa posição no array "reefIndices". Depois são geradas as coordenadas para cada coral. Cada coordenada é escolhida aleatoriamente dentro dos limites (rangeMin, rangeMax) e discretizada usando a função "u.SeInDiSp", que leva em conta o passo de discretização (rangeStep). Isso garante uma distribuição inicial uniforme e controlada das soluções (corais) no espaço de busca.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::InitReef () { // Количество начальных кораллов в рифе (исходя из rho0) int initialCorals = (int)MathRound (rho0 * totalReefSize); // Количество начальных кораллов не должно превышать размер популяции if (initialCorals > popSize) initialCorals = popSize; // Инициализируем initialCorals случайных позиций в рифе for (int i = 0; i < initialCorals; i++) { int pos; // Ищем свободную позицию do { pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Защита от выхода за пределы массива if (pos < 0) pos = 0; if (pos >= totalReefSize) pos = totalReefSize - 1; } while (occupied [pos]); // Создаем новый коралл на найденной позиции occupied [pos] = true; reefIndices [pos] = i; // Генерируем случайные координаты для нового коралла for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
O método "Moving ()" realiza a avaliação inicial da população de corais. Se "revision" tiver valor "false", o método executa uma iteração por todas as posições do recife. Para cada posição ocupada (determinada pelo valor no array "occupied"), o método obtém o índice do coral presente nessa posição a partir do array "reefIndices". Se o índice "idx" for válido, será realizada a computação da adaptabilidade desse coral.
É importante observar que o método "Moving ()" não calcula diretamente a adaptabilidade, mas apenas fornece as informações necessárias para sua computação. Após a conclusão da iteração por todas as posições do recife, o método define o valor de "revision" como "true" para impedir uma nova passagem pelo ciclo de avaliação dos corais nessa mesma iteração de otimização. Em essência, o método "Moving ()" atua como um gatilho para o cálculo da adaptabilidade dos corais, garantindo a execução única desse processo a cada iteração da otimização.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Moving () { if (!revision) { // Первичная оценка всех кораллов в рифе for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { int idx = reefIndices [i]; if (idx >= 0 && idx < popSize) { // Расчет приспособленности не требует использования GetFitness() // так как он будет вычислен во внешнем коде (в FuncTests) } } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
O método "Revision ()" atualiza a melhor solução global: procura corais no recife cuja adaptabilidade seja superior à da melhor solução global atual e a substitui. Cria um array, preparando espaço para as larvas obtidas durante a reprodução. Em seguida, o método inicia as reproduções sexuais: chama os métodos "BroadcastSpawning" e "Brooding" para criar larvas. No passo seguinte, o método realiza a fixação das larvas usando "LarvaSettling" para determinar os locais das novas larvas no recife. Depois executa a reprodução assexuada "AsexualReproduction", e no final ocorre o processo de eliminação. Em resumo: atualiza a solução, reproduz os corais, posiciona as larvas e modela o impacto da extinção.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Revision () { // Обновление глобального наилучшего решения for (int i = 0; i < totalReefSize; i++) { if (occupied [i] && a [reefIndices [i]].f > fB) { fB = a [reefIndices [i]].f; ArrayCopy (cB, a [reefIndices [i]].c, 0, 0, WHOLE_ARRAY); } } // Формируем массив для хранения личинок S_AO_Agent larvae []; ArrayResize (larvae, totalReefSize * 2); // Выделяем с запасом int larvaCount = 0; // Этап 1: Broadcast Spawning (внешнее половое размножение) BroadcastSpawning (larvae, larvaCount); // Этап 2: Brooding (внутреннее половое размножение) Brooding (larvae, larvaCount); // Вычисляем функцию приспособленности для каждой личинки // (будет выполнено в внешнем коде в FuncTests) // Этап 3: Оседание личинок for (int i = 0; i < larvaCount; i++) { LarvaSettling (larvae [i]); } // Этап 4: Бесполое размножение AsexualReproduction (); // Этап 5: Вымирание Depredation (); } //——————————————————————————————————————————————————————————————————————————————
O método "LarvaSettling" modela o processo de ocupação do recife por uma larva. Ele tenta encontrar um local adequado e, ou a fixa em um espaço livre, ou substitui um coral existente com pior adaptabilidade. Durante a tentativa de fixação, a larva tenta ocupar o recife "attemptsNum" vezes. Em cada tentativa é escolhida uma posição aleatória no recife. Se a posição estiver livre (não ocupada por um coral), o método procura um índice livre no array de agentes "a []"; se um índice livre for encontrado, a larva copia sua solução (coordenadas "c []" e adaptabilidade "f") para a célula correspondente no array de agentes.
A informação de que a posição do recife agora está ocupada é atualizada, e o método retorna o índice da posição "pos" ocupada com sucesso. Se a posição escolhida estiver ocupada, o método compara a adaptabilidade (fitness) da larva com a do coral situado nessa posição. Se a larva for melhor, ela substitui o coral existente copiando seus parâmetros para a célula correspondente no array de agentes, e o método retorna o índice "pos" da posição onde ocorreu a substituição. Se após todas as tentativas a larva não conseguir se fixar (nem em espaço livre, nem substituindo algum coral existente), o método retorna -1.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::LarvaSettling (S_AO_Agent &larva) { // Пытаемся заселить личинку attemptsNum раз for (int attempt = 0; attempt < attemptsNum; attempt++) { // Выбираем случайную позицию в рифе int pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Проверяем, что позиция находится в пределах массива if (pos < 0 || pos >= totalReefSize) continue; // Если позиция свободна, заселяем личинку if (!occupied [pos]) { // Ищем свободный индекс в массиве агентов int newIndex = -1; for (int i = 0; i < popSize; i++) { bool used = false; for (int j = 0; j < totalReefSize; j++) { if (reefIndices [j] == i) { used = true; break; } } if (!used) { newIndex = i; break; } } if (newIndex != -1) { // Копируем решение личинки ArrayCopy (a [newIndex].c, larva.c, 0, 0, WHOLE_ARRAY); a [newIndex].f = larva.f; // Обновляем информацию о рифе occupied [pos] = true; reefIndices [pos] = newIndex; return pos; } } // Если позиция занята, проверяем, лучше ли личинка текущего коралла else if (occupied [pos] && reefIndices [pos] >= 0 && reefIndices [pos] < popSize && larva.f > a [reefIndices [pos]].f) { // Личинка вытесняет существующий коралл ArrayCopy (a [reefIndices [pos]].c, larva.c, 0, 0, WHOLE_ARRAY); a [reefIndices [pos]].f = larva.f; return pos; } } // Если личинке не удалось заселиться, возвращаем -1 return -1; } //——————————————————————————————————————————————————————————————————————————————
O método "BroadcastSpawning" modela a reprodução externa dos corais por meio do processo de desova. Ele executa as seguintes etapas principais: identifica os índices de todos os locais ocupados por corais no recife, determina a quantidade de corais que participarão da desova com base no parâmetro "Fb" (Brooding Fraction) — a fração de corais que participam da reprodução externa —, embaralha os índices dos corais ocupados e então seleciona pares para o processo de desova. Criação de larvas por cruzamento: para cada par de corais é criada uma nova larva, cujas coordenadas são calculadas como o valor médio das coordenadas dos pais, com a adição de uma pequena mutação aleatória. Esse processo de cruzamento (crossover) busca unir as melhores características dos pais; as larvas produzidas são adicionadas ao array "larvae".
Pontos importantes:
- "Fb" aqui define a fração de corais que participam da reprodução externa (desova), diferentemente de "Brooding", onde controla a fração de corais envolvidos na reprodução interna.
- O cruzamento e a mutação aumentam a diversidade genética da população.
- O objetivo do método é criar novas larvas obtidas pela combinação dos genes dos corais pais, para posterior colonização do recife. O método pressupõe cruzamento em pares.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount) { // Находим все занятые позиции int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Проверка на случай, если нет занятых позиций if (occupiedCount == 0) return; // Выбираем долю Fb для внешнего размножения int broadcastCount = (int)MathRound (Fb * occupiedCount); if (broadcastCount <= 0) broadcastCount = 1; // Минимум один коралл if (broadcastCount > occupiedCount) broadcastCount = occupiedCount; // Перемешиваем индексы for (int i = 0; i < occupiedCount; i++) { // Фиксируем проблему выхода за пределы массива int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Гарантируем, что j в пределах массива if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Образуем пары и создаем потомство for (int i = 0; i < broadcastCount - 1; i += 2) { if (i + 1 < broadcastCount) // Проверяем, что есть второй родитель { int idx1 = reefIndices [occupiedIndices [i]]; int idx2 = reefIndices [occupiedIndices [i + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) { // Инициализируем личинку larvae [larvaCount].Init (coords); // Создаем новую личинку как результат скрещивания for (int c = 0; c < coords; c++) { // Простой метод скрещивания: среднее значение координат родителей с небольшой мутацией double value = (a [idx1].c [c] + a [idx2].c [c]) / 2.0 + u.RNDfromCI (-0.1, 0.1) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Увеличиваем счетчик личинок larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
O método "Brooding" imita o processo de desenvolvimento interno das larvas nos corais dentro do CRO e executa as seguintes etapas:
- determina quais posições do recife estão ocupadas por corais e armazena os índices dessas posições.
- calcula quantos corais participarão do desenvolvimento interno das larvas usando o parâmetro "Fb" (Brooding Fraction). Para selecionar aleatoriamente os corais participantes, os índices das posições ocupadas são embaralhados.
- cria e muta larvas: para cada coral selecionado é criada uma larva. A larva é inicializada e mutada: suas coordenadas são ligeiramente alteradas de forma aleatória em relação às do coral pai. As larvas mutadas são adicionadas ao array "larvae".
Pontos importantes:
- "Fb" define a fração de corais que NÃO participam da reprodução assexuada (ou seja, os que participam do desenvolvimento interno).
- A mutação garante diversidade genética na população de larvas.
- O objetivo é criar novos indivíduos potencialmente melhores, que irão competir por vagas no recife.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Brooding (S_AO_Agent &larvae [], int &larvaCount) { // Находим все занятые позиции int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Проверка на случай, если нет занятых позиций if (occupiedCount == 0) return; // Количество кораллов для внутреннего размножения int broodingCount = (int)MathRound ((1.0 - Fb) * occupiedCount); if (broodingCount <= 0) broodingCount = 1; // Минимум один коралл if (broodingCount > occupiedCount) broodingCount = occupiedCount; // Перемешиваем индексы for (int i = 0; i < occupiedCount; i++) { // Фиксируем проблему выхода за пределы массива int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Гарантируем, что j в пределах массива if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Для каждого выбранного коралла создаем мутированную копию for (int i = 0; i < broodingCount; i++) { if (i < occupiedCount) // Проверка на выход за границы { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Инициализируем личинку larvae [larvaCount].Init (coords); // Создаем новую личинку как мутацию исходного коралла for (int c = 0; c < coords; c++) { // Мутация: добавляем небольшое случайное отклонение double value = a [idx].c [c] + u.RNDfromCI (-0.2, 0.2) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Увеличиваем счетчик личинок larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
O método "AsexualReproduction" modela a reprodução assexuada dos corais por brotamento. O método realiza as seguintes etapas: identifica os índices de todas as posições do recife ocupadas por corais, ordena esses índices em ordem decrescente de adaptabilidade, ou seja, primeiro aparecem as posições com os corais mais adaptados. Com base no parâmetro "Fa" (Fraction for Asexual reproduction), que define a fração de corais participantes da reprodução assexuada, determina-se quantos dos melhores corais irão produzir clones. Criação e fixação dos clones: para cada coral selecionado é criada uma cópia exata (clone), isto é, uma larva com as mesmas coordenadas e adaptabilidade. O método "LarvaSettling" é chamado para tentar fixar o clone no recife.
Pontos importantes:
- A reprodução assexuada permite que os corais mais adaptados espalhem rapidamente seus genes.
- O parâmetro "Fa" controla a intensidade da reprodução assexuada.
- O uso de "LarvaSettling" para a fixação dos clones significa que os clones devem competir por espaço no recife da mesma forma que as larvas obtidas por reprodução sexual.
- O método de clonagem, neste caso, é uma cópia exata do pai SEM mutações. As mutações ocorrem apenas na reprodução sexual.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::AsexualReproduction () { // Находим все занятые позиции и их индексы int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности SortAgentsByFitness (occupiedIndices, occupiedCount); // Выбираем лучшие Fa% кораллов для бесполого размножения int budCount = (int)MathRound (Fa * occupiedCount); if (budCount <= 0) budCount = 1; // Минимум один коралл if (budCount > occupiedCount) budCount = occupiedCount; // Для каждого выбранного коралла создаем клон и пытаемся заселить его for (int i = 0; i < budCount; i++) { if (i < occupiedCount) // Проверка на выход за границы { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Создаем новую личинку как точную копию исходного коралла S_AO_Agent clone; clone.Init (coords); ArrayCopy (clone.c, a [idx].c, 0, 0, WHOLE_ARRAY); clone.f = a [idx].f; // Пытаемся заселить клон LarvaSettling (clone); } } } } //——————————————————————————————————————————————————————————————————————————————
O método "Depredation" modela o processo de extinção dos corais devido à predação ou outros fatores negativos (por exemplo, poluição). Neste caso, a eliminação é aplicada com probabilidade "Pd". Se um número aleatório for menor que "Pd", então o processo de eliminação é realizado. A busca por posições ocupadas identifica os índices de todas as posições do recife que estão ocupadas por corais. Os índices dessas posições são ordenados pela adaptabilidade (fitness) dos corais.
O array ordenado de índices é invertido, de modo que no início do array fiquem os índices dos corais menos adaptados. É determinado o número de corais que serão removidos com base no parâmetro "Fd" (Fraction for Depredation). Esse valor é arredondado para um número inteiro. O número especificado de corais menos adaptados é então removido. Em seguida, ocorre a limpeza do recife: para cada posição marcada para remoção: a célula correspondente no array "occupied" é definida como "false", indicando que agora a posição está livre. A célula correspondente no array "reefIndices" é definida como -1, indicando a ausência de um coral nessa posição.
//—————————————————————————————————————————————————————————————————————————————— oid C_AO_CRO::Depredation() { // Применяем уничтожение с вероятностью Pd if (u.RNDfromCI(0, 1) < Pd) { // Находим все занятые позиции и их индексы int occupiedIndices[]; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied[i]) { ArrayResize(occupiedIndices, occupiedCount + 1); occupiedIndices[occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности SortAgentsByFitness(occupiedIndices, occupiedCount); // Переворачиваем массив, чтобы худшие были первыми for (int i = 0; i < occupiedCount / 2; i++) { if(i < occupiedCount && (occupiedCount - 1 - i) < occupiedCount) // Проверка на выход за границы { int temp = occupiedIndices[i]; occupiedIndices[i] = occupiedIndices[occupiedCount - 1 - i]; occupiedIndices[occupiedCount - 1 - i] = temp; } } // Удаляем худшие Fd% кораллов int removeCount = (int)MathRound(Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // Минимум один коралл if (removeCount > occupiedCount) removeCount = occupiedCount; // Защита от переполнения for (int i = 0; i < removeCount; i++) { if(i < occupiedCount) // Проверка на выход за границы { int pos = occupiedIndices[i]; if(pos >= 0 && pos < totalReefSize) // Дополнительная проверка { occupied[pos] = false; reefIndices[pos] = -1; } } } } } //——————————————————————————————————————————————————————————————————————————————
Método "GetReefCoordIndex" converte as coordenadas do recife (linha e coluna) em um índice unidimensional e recebe "row" e "col" como entradas, retornando o índice correspondente no array que representa o recife. Primeiro, o método verifica se as coordenadas fornecidas não ultrapassam os limites do recife. Caso estejam dentro dos limites, o índice é calculado usando a fórmula (row * reefCols + col), onde "reefCols" é o número de colunas no recife. Esse método é usado para acessar os elementos nos arrays que representam o recife.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::GetReefCoordIndex (int row, int col) { // Проверка на выход за границы if (row < 0 || row >= reefRows || col < 0 || col >= reefCols) return -1; // Переводим двухмерную позицию в одномерный индекс return row * reefCols + col; } //——————————————————————————————————————————————————————————————————————————————
Método "SortAgentsByFitness" ordena o array de índices "indices" contendo "count" elementos correspondentes a corais, em ordem decrescente de adaptabilidade (fitness), usando o algoritmo de ordenação por bolha, A ordenação é realizada com base nos valores de adaptabilidade armazenados no array "a", acessado por meio do array "reefIndices". Dessa forma, após a execução do método, "indices" contém os índices dos corais organizados do mais adaptado ao menos adaptado. Verificações adicionais são incluídas para evitar acessos fora dos limites dos arrays.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::SortAgentsByFitness (int &indices [], int &count) { // Проверка на пустой массив if (count <= 0) return; // Сортировка пузырьком по убыванию приспособленности for (int i = 0; i < count - 1; i++) { for (int j = 0; j < count - i - 1; j++) { if (j + 1 < count) // Проверка, чтобы j+1 не выходил за пределы { int idx1 = reefIndices [indices [j]]; int idx2 = reefIndices [indices [j + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) // Проверка индексов { if (a [idx1].f < a [idx2].f) { int temp = indices [j]; indices [j] = indices [j + 1]; indices [j + 1] = temp; } } } } } } //——————————————————————————————————————————————————————————————————————————————
Concluímos a preparação do algoritmo, descrevemos no código todos os seus numerosos métodos de funcionamento, e agora podemos passar diretamente para os testes.
Resultados dos testes
Após os testes realizados, pode-se observar que o algoritmo CRO apresenta desempenho bastante fraco e é necessário revisar alguns métodos do procedimento original.CRO|Coral Reef Optimization|50.0|5.0|5.0|0.4|0.9|0.1|0.1|0.01|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.365266682511984
25 Hilly's; Func runs: 10000; result: 0.270828009448956
500 Hilly's; Func runs: 10000; result: 0.2504192846772352
=============================
5 Forest's; Func runs: 10000; result: 0.23618879234608753
25 Forest's; Func runs: 10000; result: 0.19453106526100442
500 Forest's; Func runs: 10000; result: 0.1679109693993047
=============================
5 Megacity's; Func runs: 10000; result: 0.13076923076923075
25 Megacity's; Func runs: 10000; result: 0.11138461538461542
500 Megacity's; Func runs: 10000; result: 0.09366153846153921
=============================
All score: 1.82096 (20.23%)
Antes de tudo, o que me chamou atenção no algoritmo CRO foi o método de eliminação. Ele precisa ser modificado para melhorar a busca; iremos substituir os piores corais do recife por novos, que serão gerados na vizinhança dos melhores corais (soluções), promovendo assim a busca em direção a regiões mais promissoras. Definimos a quantidade de melhores corais "eliteCount" e a quantidade de piores corais "removeCount".
Substituição das piores soluções: para cada "vítima" é escolhido um coral "elite", e é gerado um novo coral na vizinhança desse coral "elite". No mecanismo aprimorado de eliminação aplicamos uma distribuição de potência inversa com expoente 10 (onde power = 0.1) para gerar desvios em relação ao melhor coral. Essa distribuição é caracterizada por gerar a maioria das novas soluções muito próximas do melhor coral, mas com pequena probabilidade de produzir desvios significativos, o que assegura o equilíbrio entre a busca local (intensificação) e a exploração global do espaço de soluções. As novas coordenadas são limitadas ao intervalo permitido. A posição liberada no recife é então ocupada pelo novo coral.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Depredation () { // Применяем уничтожение с вероятностью Pd if (u.RNDfromCI (0, 1) < Pd) { // Находим все занятые позиции и их индексы int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности (от лучших к худшим) SortAgentsByFitness (occupiedIndices, occupiedCount); // Определяем количество лучших решений, используемых для генерации новых int eliteCount = (int)MathRound (0.1 * occupiedCount); // Используем 10% лучших if (eliteCount <= 0) eliteCount = 1; // Минимум одно элитное решение if (eliteCount > occupiedCount) eliteCount = occupiedCount; // Определяем количество худших решений для замены int removeCount = (int)MathRound (Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // Минимум одно решение заменяем if (removeCount > occupiedCount - eliteCount) removeCount = occupiedCount - eliteCount; // Не удаляем элитные решения // Удаляем худшие решения и заменяем их новыми в окрестности лучших for (int i = 0; i < removeCount; i++) { // Индекс удаляемого решения (с конца отсортированного массива) int removeIndex = occupiedCount - 1 - i; if (removeIndex < 0 || removeIndex >= occupiedCount) continue; int posToRemove = occupiedIndices [removeIndex]; if (posToRemove < 0 || posToRemove >= totalReefSize) continue; // Выбираем одно из элитных решений double power = 0.1; // Параметр степенного распределения double r = u.RNDfromCI (0, 1); int eliteIdx = (int)(eliteCount); if (eliteIdx >= eliteCount) eliteIdx = eliteCount - 1; int posBest = occupiedIndices [eliteIdx]; if (posBest < 0 || posBest >= totalReefSize) continue; int bestAgentIdx = reefIndices [posBest]; if (bestAgentIdx < 0 || bestAgentIdx >= popSize) continue; // Освобождаем позицию для нового решения occupied [posToRemove] = false; // Генерируем новое решение в окрестности выбранного элитного решения int newAgentIdx = reefIndices [posToRemove]; // Используем тот же индекс агента if (newAgentIdx >= 0 && newAgentIdx < popSize) { // Генерация через степенное распределение вокруг лучшего решения for (int c = 0; c < coords; c++) { // Определяем радиус поиска (можно адаптировать в зависимости от прогресса) double radius = 0.7 * (rangeMax [c] - rangeMin [c]); // 10% от диапазона // Генерируем значение по степенному закону double sign = u.RNDfromCI (0, 1) < 0.5 ? -1.0 : 1.0; // Случайный знак double deviation = sign * radius * MathPow (u.RNDfromCI (0, 1), 1.0 / power); // Новое значение в окрестности лучшего double newValue = a [bestAgentIdx].c [c] + deviation; // Ограничиваем значение в допустимом диапазоне a [newAgentIdx].c [c] = u.SeInDiSp (newValue, rangeMin [c], rangeMax [c], rangeStep [c]); } // Заселяем новое решение в риф occupied [posToRemove] = true; reefIndices [posToRemove] = newAgentIdx; } } } } //——————————————————————————————————————————————————————————————————————————————
Agora, após as modificações realizadas, testamos o algoritmo CROm. Como pode ser observado nos resultados abaixo, o algoritmo melhorou significativamente seu desempenho.
CROm|Coral Reef Optimization M|50.0|20.0|20.0|0.2|0.99|0.01|0.8|0.9|20.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7851210159578113
25 Hilly's; Func runs: 10000; result: 0.4603296933002806
500 Hilly's; Func runs: 10000; result: 0.25958379129490083
=============================
5 Forest's; Func runs: 10000; result: 0.8668751980437325
25 Forest's; Func runs: 10000; result: 0.3529695710837671
500 Forest's; Func runs: 10000; result: 0.16267582083006701
=============================
5 Megacity's; Func runs: 10000; result: 0.6323076923076923
25 Megacity's; Func runs: 10000; result: 0.2673846153846154
500 Megacity's; Func runs: 10000; result: 0.10733846153846247
=============================
All score: 3.89459 (43.27%)
A visualização do algoritmo não é especial, mas é um pouco mais difícil para o algoritmo lidar com problemas discretos na função de teste "Megacity".
CROm na função de teste Hilly
CROm na função de teste Forest
CROm na função de teste Megacity
De acordo com os resultados do teste, o algoritmo CROm está na 42ª posição da tabela de classificação dos algoritmos de otimização baseados em população.
| № | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 2 | CLA | code lock algorithm (joo) | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 3 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 7 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 8 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 9 | AAm | archery algorithm M | 0,91744 | 0,70876 | 0,42160 | 2,04780 | 0,92527 | 0,75802 | 0,35328 | 2,03657 | 0,67385 | 0,55200 | 0,23738 | 1,46323 | 5,548 | 61,64 |
| 10 | ESG | evolution of social groups (joo) | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 11 | SIA | simulated isotropic annealing (joo) | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 12 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 13 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 14 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 15 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 16 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 17 | AOSm | atomic orbital search M | 0,80232 | 0,70449 | 0,31021 | 1,81702 | 0,85660 | 0,69451 | 0,21996 | 1,77107 | 0,74615 | 0,52862 | 0,14358 | 1,41835 | 5,006 | 55,63 |
| 18 | TSEA | turtle shell evolution algorithm (joo) | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 19 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 20 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 21 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 22 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 23 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 24 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 25 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 26 | BCOm | bacterial chemotaxis optimization M | 0,75953 | 0,62268 | 0,31483 | 1,69704 | 0,89378 | 0,61339 | 0,22542 | 1,73259 | 0,65385 | 0,42092 | 0,14435 | 1,21912 | 4,649 | 51,65 |
| 27 | ABO | african buffalo optimization | 0,83337 | 0,62247 | 0,29964 | 1,75548 | 0,92170 | 0,58618 | 0,19723 | 1,70511 | 0,61000 | 0,43154 | 0,13225 | 1,17378 | 4,634 | 51,49 |
| 28 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 29 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 30 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 31 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 32 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 33 | AEO | artificial ecosystem-based optimization algorithm | 0,91380 | 0,46713 | 0,26470 | 1,64563 | 0,90223 | 0,43705 | 0,21400 | 1,55327 | 0,66154 | 0,30800 | 0,28563 | 1,25517 | 4,454 | 49,49 |
| 34 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 35 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| 36 | SOA | simple optimization algorithm | 0,91520 | 0,46976 | 0,27089 | 1,65585 | 0,89675 | 0,37401 | 0,16984 | 1,44060 | 0,69538 | 0,28031 | 0,10852 | 1,08422 | 4,181 | 46,45 |
| 37 | ABHA | artificial bee hive algorithm | 0,84131 | 0,54227 | 0,26304 | 1,64663 | 0,87858 | 0,47779 | 0,17181 | 1,52818 | 0,50923 | 0,33877 | 0,10397 | 0,95197 | 4,127 | 45,85 |
| 38 | ACMO | atmospheric cloud model optimization | 0,90321 | 0,48546 | 0,30403 | 1,69270 | 0,80268 | 0,37857 | 0,19178 | 1,37303 | 0,62308 | 0,24400 | 0,10795 | 0,97503 | 4,041 | 44,90 |
| 39 | ADAMm | adaptive moment estimation M | 0,88635 | 0,44766 | 0,26613 | 1,60014 | 0,84497 | 0,38493 | 0,16889 | 1,39880 | 0,66154 | 0,27046 | 0,10594 | 1,03794 | 4,037 | 44,85 |
| 40 | CGO | chaos game optimization | 0,57256 | 0,37158 | 0,32018 | 1,26432 | 0,61176 | 0,61931 | 0,62161 | 1,85267 | 0,37538 | 0,21923 | 0,19028 | 0,78490 | 3,902 | 43,35 |
| 41 | ATAm | artificial tribe algorithm M | 0,71771 | 0,55304 | 0,25235 | 1,52310 | 0,82491 | 0,55904 | 0,20473 | 1,58867 | 0,44000 | 0,18615 | 0,09411 | 0,72026 | 3,832 | 42,58 |
| 42 | CROm | coral reefs optimization M | 0,78512 | 0,46032 | 0,25958 | 1,50502 | 0,86688 | 0,35297 | 0,16267 | 1,38252 | 0,63231 | 0,26738 | 0,10734 | 1,00703 | 3,895 | 43,27 |
| 43 | CFO | central force optimization | 0,60961 | 0,54958 | 0,27831 | 1,43750 | 0,63418 | 0,46833 | 0,22541 | 1,32792 | 0,57231 | 0,23477 | 0,09586 | 0,90294 | 3,668 | 40,76 |
| 44 | ASHA | artificial showering algorithm | 0,89686 | 0,40433 | 0,25617 | 1,55737 | 0,80360 | 0,35526 | 0,19160 | 1,35046 | 0,47692 | 0,18123 | 0,09774 | 0,75589 | 3,664 | 40,71 |
| 45 | ASBO | adaptive social behavior optimization | 0,76331 | 0,49253 | 0,32619 | 1,58202 | 0,79546 | 0,40035 | 0,26097 | 1,45677 | 0,26462 | 0,17169 | 0,18200 | 0,61831 | 3,657 | 40,63 |
| RW | neuroboids optimization algorithm 2(joo) | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Considerações finais
Os recifes de coral vivos representam um sistema delicadamente equilibrado, onde é continuamente mantido um balanço entre estabilidade e variabilidade, entre preservar estratégias de sobrevivência comprovadas e experimentar novas. O mecanismo modificado de extinção, com a geração de novas soluções na vizinhança das melhores, imita o processo natural de sucesso ecológico nos recifes de coral.
Na natureza, após a morte de algumas colônias, as áreas liberadas do recife não são ocupadas por espécies aleatórias, mas por aquelas que apresentam melhor adaptação às condições locais. Além disso, a sobrevivência de novas colônias é maior nas zonas próximas às colônias bem-sucedidas já existentes, o que é diretamente refletido no algoritmo por meio da geração de novas soluções ao redor das elites. Isso garante a exploração contínua de regiões promissoras do espaço de busca e mantém inalterado o tamanho da população.
A implementação da distribuição de potência inversa (com expoente 10, onde power = 0.1) permite gerar desvios em relação ao melhor coral. Esse tipo de distribuição concentra a maioria das novas soluções próximas do melhor coral, com raros desvios significativos, garantindo um equilíbrio ideal entre intensificação local e diversificação global.
A ampliação do raio de busca para 70% do intervalo permitido possibilita ao algoritmo explorar áreas mais amplas do espaço de soluções.
O uso apenas das melhores soluções (a elite) como base para gerar novos candidatos acelera a convergência em direção às regiões ótimas e melhora a qualidade das soluções obtidas, enquanto os diversos operadores que modelam aspectos-chave da evolução dos corais (reprodução externa e interna, fixação de larvas e reprodução assexuada) podem ser aplicados no desenvolvimento de outros métodos populacionais de otimização.
Figura 2. Classificação colorida dos algoritmos de acordo com os testes correspondentes
Figura 3. Histograma dos resultados de testes dos algoritmos (em escala de 0 a 100, quanto maior melhor, onde 100 é o resultado teórico máximo possível, no arquivo compactado há um script para calcular a tabela de classificação)
Prós e contras do algoritmo CROm:
Prós:
- Ideia interessante.
- Desenvolvimento promissor.
- Resultados estáveis.
Contras:
- Resultados mais fracos em funções discretas.
- Grande quantidade de parâmetros externos.
Um arquivo com as versões atuais dos códigos dos algoritmos está anexado ao artigo. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, já que muitos deles foram modificados para melhorar suas capacidades de busca. As conclusões e julgamentos apresentados no artigo baseiam-se nos resultados dos experimentos realizados.
Programas utilizados no artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | #C_AO.mqh | Arquivo incluído | Classe pai dos algoritmos populacionais de otimização |
| 2 | #C_AO_enum.mqh | Arquivo incluído | Enumeração dos algoritmos populacionais de otimização |
| 3 | TestFunctions.mqh | Arquivo incluído | Biblioteca de funções de teste |
| 4 | TestStandFunctions.mqh | Arquivo incluído | Biblioteca de funções do test stand |
| 5 | Utilities.mqh | Arquivo incluído | Biblioteca de funções auxiliares |
| 6 | CalculationTestResults.mqh | Arquivo incluído | Script para calcular resultados na tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Test stand unificado para todos os algoritmos populacionais de otimização |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Exemplo simples de uso de algoritmos populacionais de otimização sem visualização |
| 9 | Test_AO_CROm.mq5 | Script | Test stand para CROm |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/17760
Aviso: Todos os direitos sobre esses materiais pertencem à MetaQuotes Ltd. É proibida a reimpressão total ou parcial.
Esse artigo foi escrito por um usuário do site e reflete seu ponto de vista pessoal. A MetaQuotes Ltd. não se responsabiliza pela precisão das informações apresentadas nem pelas possíveis consequências decorrentes do uso das soluções, estratégias ou recomendações descritas.
Redes neurais em trading: Ator–Diretor–Crítico (Actor–Director–Critic)
Trading por algoritmo: IA e seu caminho para os topos dourados
Construa Expert Advisors Auto-Otimizáveis em MQL5 (Parte 2): Estratégia de Scalping USDJPY
Desenvolvimento do Kit de Ferramentas de Análise de Price Action (Parte 5): Volatility Navigator EA
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso