Otimização por Comunidade de Cientistas - Community of Scientist Optimization (CoSO): Teoria
12
0
Conteúdo
Introdução
Neste artigo, examinamos em detalhe para a solução de problemas de otimização: o algoritmo CoSO (Community of Scientist Optimization), baseado na modelagem dos mecanismos de funcionamento da comunidade científica. Diferentemente dos algoritmos clássicos de inspiração biológica, o CoSO reproduz características únicas da atividade científica: a publicação de resultados em periódicos, o concurso por bolsas de pesquisa, a formação de grupos de pesquisa e o equilíbrio entre o aprofundamento de linhas de pesquisa já conhecidas e a busca de soluções fundamentalmente novas. O algoritmo CoSO foi desenvolvido e publicado em 2012 por dois cientistas, A. Milani e V. Santucci.
Uma característica interessante dessa abordagem é que a busca se auto-organiza naturalmente. Assim como em uma comunidade científica real, o algoritmo concentra recursos em áreas promissoras, preserva e dissemina as melhores soluções por meio do mecanismo de publicação em periódicos e mantém a diversidade necessária por meio do financiamento de "outsiders". A variação dinâmica do tamanho da população permite que o algoritmo se adapte às características de cada problema sem exigir ajuste fino de parâmetros. Essa é mais uma inovação, já que normalmente usamos uma população constante. Neste artigo, examinaremos em detalhe os fundamentos matemáticos do algoritmo, seus componentes principais e os mecanismos de interação entre eles.
Implementação do algoritmo
O CoSO parte da ideia de modelar o comportamento de pesquisadores que buscam soluções ótimas em um espaço multidimensional, trocam conhecimento por meio de publicações em periódicos e competem por recursos limitados (financiamentos de pesquisa). Cada pesquisador é um ponto no espaço de busca. Ele possui: posição (onde busca), direção de movimento, recursos para pesquisa e, se esses recursos se esgotam, o pesquisador se torna inativo.
Cada pesquisador é representado por um conjunto de parâmetros: posição no espaço de busca x, direção de movimento v, melhor resultado pessoal b, quantidade de recursos m, estratégia de gestão de recursos s e probabilidades de publicação em diferentes periódicos ρ.
O movimento dos pesquisadores é determinado pela fórmula de atualização da direção, que combina três componentes: inércia (a tendência de continuar se movendo na direção anterior), componente cognitivo (a busca pelo melhor resultado pessoal) e componente social (a influência dos melhores resultados publicados nos periódicos):
v {i, t} = ω · v {i, t-1} + φ₁ · β₁ · (b {i, t-1} - x {i, t-1}) + φ₂ · β₂ · Σⱼ [ρᵢⱼ · (J {j,c} - x {i, t-1})],
onde ω = 0.7298 é o coeficiente de inércia, φ₁ = φ₂ = 1.49618 são os coeficientes de aceleração, β₁ e β₂ são números aleatórios em [0,1], ρᵢⱼ é a probabilidade de o pesquisador i escolher o periódico j, e J {j,c} é um artigo aleatório do periódico j.
Após a atualização da direção, a posição do pesquisador é dada por: x {i, t} = x {i, t-1} + v {i, t}.
Os periódicos armazenam as melhores soluções encontradas. Os pesquisadores leem os periódicos e se deslocam em direção a boas soluções, e apenas os melhores resultados são publicados. No algoritmo, os periódicos funcionam como memória coletiva, armazenando as k melhores soluções encontradas por todos os pesquisadores. Quando um pesquisador obtém um novo resultado, ele o submete a um dos periódicos de acordo com sua distribuição de probabilidades ρ, e o periódico só aceita o resultado se ele for melhor que o pior entre os já publicados. Isso garante a melhoria contínua da qualidade da informação disponível para a comunidade.
Pesquisadores bem-sucedidos recebem mais recursos. Parte dos recursos é destinada aos "outsiders", novos pesquisadores em posições aleatórias. Isso ajuda a evitar o aprisionamento em ótimos locais. O mecanismo de distribuição de recursos imita o financiamento competitivo na ciência. Em cada iteração, os pesquisadores gastam uma unidade de recursos, e o total de recursos gastos é redistribuído com base em uma seleção por roleta baseada em ranking. A probabilidade de um pesquisador na posição i do ranking global receber recursos é determinada pela fórmula:
P (i) = (N - i + 1) / (N · (N + 1) / 2),
onde N é o número de pesquisadores.
Parte dos recursos Ω é reservada para a criação de "outsiders", novos pesquisadores em posições aleatórias. O parâmetro Ω varia adaptativamente para manter o equilíbrio entre exploração e intensificação. Quando σ, o desvio padrão dos valores de fitness da população, cai abaixo de σ₀, isso sinaliza convergência, e a proporção de outsiders aumenta:
Ω {t} = Ω {t-1} + (Ω {max} - Ω {min}) / 2 · ε⁺ se σ < σ₀, caso contrário Ω {t} = Ω {t-1} - (Ω {max} - Ω {min}) / 2 · ε⁻,
onde Ω {min} = 0.2, Ω {max} = 0.5, ε⁺ = 0.2, ε⁻ = 0.1.
Cientistas bem-sucedidos podem contratar assistentes, que iniciam a busca nas proximidades do supervisor. Isso ajuda a explorar em detalhe áreas promissoras. Pesquisadores bem-sucedidos com quantidade de recursos m > 1 podem contratar novos pesquisadores. Nesse caso, o pesquisador mantém para si uma parte dos recursos, de acordo com sua estratégia s, e gasta o restante na contratação.
Os novos pesquisadores herdam as características do supervisor com pequenas perturbações: a posição é inicializada como x {new} = x {supervisor} + N (0, σv), a estratégia como s {new} = N (s {supervisor}, σs), e as probabilidades dos periódicos como ρ {new, j} = N (ρ {supervisor, j}, σρ), com normalização posterior.
A dinâmica de busca no algoritmo pode ser comparada à coleta de cogumelos na floresta por um grupo de pessoas: cada um procura em sua própria área e, quando alguém encontra um bom local de coleta, chama os demais; então uma parte do grupo vai até ele, enquanto outra continua procurando novos lugares. Aqueles que passam muito tempo sem encontrar nada vão embora para casa, mas os catadores de cogumelos mais bem-sucedidos levam amigos para esses pontos.
O desempenho do algoritmo decorre da combinação de vários mecanismos: os periódicos promovem a troca de informações e direcionam a busca para áreas promissoras, o financiamento competitivo cria pressão seletiva ao eliminar pesquisadores ineficientes, a contratação de assistentes permite a busca local em torno de boas soluções, e os outsiders evitam a convergência prematura.
A variação dinâmica do tamanho da população permite que o algoritmo se adapte à complexidade do problema, aumentando o número de pesquisadores em áreas promissoras e reduzindo-o nas áreas pouco promissoras. Todos esses mecanismos atuam em conjunto, criando um sistema que se auto-organiza e é capaz de resolver problemas em espaços multidimensionais complexos.
Figura 1. Ilustração do funcionamento do algoritmo CoSO
O que a ilustração mostra:
- Espaço de busca (Search Space), com pesquisadores (círculos verdes) movendo-se em direção ao ótimo e seus vetores de movimento indicados.
- Periódicos científicos (Scientific Journals) armazenam as melhores soluções encontradas; os pesquisadores os leem e publicam seus resultados.
- Distribuição de recursos (Funds Distribution) - mecanismo de financiamento, em espaços multidimensionais, com parâmetro adaptativo Ω para outsiders.
- Fórmula de atualização da direção - base matemática do movimento dos pesquisadores.
- Mecanismos-chave - legenda com os tipos de pesquisadores: ativos (com recursos), inativos (sem recursos), novas contratações e outsiders em posições aleatórias.
As setas indicam os fluxos de informação (cinza), de movimento (azul) e de recursos (laranja). Agora, passamos para a escrita do pseudocódigo do algoritmo.
1. INICIALIZAÇÃO:
- Criar 10 pesquisadores em posições aleatórias
- Dar a cada um 15 unidades de recursos (150 / 10)
- Cada um recebe:
- Estratégia aleatória de economia de recursos (de 0 a 1)
- Preferências aleatórias por periódicos
- Direção inicial de movimento (pequena e aleatória)
- Criar 3 periódicos vazios
- Registrar a dispersão inicial da população
2. CICLO PRINCIPAL (repetir o número de vezes especificado):
2.1. AVALIAÇÃO DOS RESULTADOS:
Para cada pesquisador ativo:
- Calcular a qualidade da posição atual f(x)
- Se o resultado for melhor que o melhor resultado pessoal:
* Atualizar o melhor resultado pessoal
2.2. PUBLICAÇÃO NOS PERIÓDICOS:
Para cada pesquisador ativo:
- Escolher um periódico de acordo com as preferências pessoais
- Tentar publicar o resultado:
* O periódico aceita se o resultado estiver entre os 10 melhores
* O pior artigo é removido
2.3. CONTROLE DE GASTOS E PRESTAÇÃO DE CONTAS:
- Reunir todos os recursos gastos (1 de cada pesquisador)
- Montar o ranking dos pesquisadores ativos
- Marcar como "inativos" aqueles que ficaram sem recursos
2.4. DISTRIBUIÇÃO DO FINANCIAMENTO:
- Determinar a parcela destinada aos outsiders (20-50%)
- Distribuir o restante entre os pesquisadores existentes:
* Quanto mais alta a posição no ranking, maiores as chances
* Usar seleção por roleta ponderada
2.5. CRIAÇÃO DE OUTSIDERS:
- Alocar os recursos reservados à criação de 1 a 5 novatos
- Colocá-los em posições aleatórias
- Atribuir a eles parcelas iguais do orçamento reservado
2.6. CONTRATAÇÃO DE ASSISTENTES:
Para cada pesquisador com recursos > 1:
- Reservar para si uma parte, de acordo com a estratégia
- Com o restante, contratar de 1 a 3 assistentes:
* Posicioná-los nas proximidades do pesquisador
* Transmitir sua experiência com pequenas variações
2.7. ESCOLHA DA DIREÇÃO DE MOVIMENTO:
Para cada pesquisador ativo, calcular:
Nova_direção =
0.7 × Direção_anterior + // Inércia
1.5 × Aleatoriedade × (Melhor_resultado_pessoal - Posição) + // Em direção ao seu melhor resultado
1.5 × Aleatoriedade × Soma_dos_periódicos // Em direção aos melhores resultados dos periódicos
(Peso_do_periódico × (Artigo_do_periódico - Posição))
2.8. MOVIMENTO:
Para cada pesquisador ativo:
- Efetuar o deslocamento: Nova_posição = Posição_anterior + Direção
- Se sair dos limites, reposicionar no limite
2.9. CONTROLE DA DIVERSIDADE:
- Medir a dispersão atual da população
- Se a dispersão diminuir (há convergência):
* Aumentar a parcela de outsiders em 10%
- Caso contrário:
* Reduzir a parcela de outsiders em 5%
2.10. GESTÃO DO TAMANHO DA POPULAÇÃO:
- Se a proporção de inativos exceder 25% ou se o total ultrapassar 200:
* Remover os inativos do array
- Se restarem mais de 150:
* Manter apenas os 150 melhores
3. RESULTADO:
- Retornar a melhor solução encontrada
Agora podemos passar para a implementação prática do algoritmo CoSO. Vamos definir três estruturas de dados. A primeira estrutura, "S_Journal_Entry", representa uma entrada individual no periódico e contém:
- fitness - valor numérico que reflete a qualidade dessa entrada.
- decision [] - array dinâmico que armazena os parâmetros associados a essa entrada.
- entries [] - array dinâmico de entradas "S_Journal_Entry".
- length - número atual de entradas no periódico.
- maxLength - número máximo de entradas que o periódico pode armazenar.
O método "Init" inicializa o periódico, definindo o tamanho máximo, alocando memória para as entradas e inicializando cada entrada com um valor mínimo de fitness. O método "Add" é usado para adicionar uma nova entrada ao periódico. A particularidade desse método é que ele mantém o periódico ordenado pelo valor de fitness. Se a nova entrada for pior do que a pior entrada de um periódico já cheio, ela não será adicionada. Caso contrário, a posição da nova entrada é encontrada por meio de busca binária; em seguida, as entradas existentes são deslocadas para abrir espaço, e a nova entrada é inserida. Se o periódico ainda não estiver cheio, "length" é incrementado.
A terceira estrutura, "S_Researcher", descreve o "pesquisador" ou "agente". Ela contém um conjunto de parâmetros:
- x [] - posição atual do pesquisador (array de coordenadas)
- v [] - direção ou vetor de velocidade do pesquisador
- b [] - melhor posição encontrada individualmente por esse pesquisador
- rho [] - array de probabilidades de publicação em diferentes periódicos. O pesquisador interage com vários "periódicos" ou fontes de informação
- s - estratégia de gestão de recursos
- m - quantidade de recursos (número inteiro)
- f - fitness da posição atual do pesquisador
- fb - fitness da melhor posição encontrada pelo pesquisador
- alive - flag que indica se o pesquisador está ativo
//———————————————————————————————————————————————————————————————————— // Структура для журнала struct S_Journal_Entry { double fitness; double decision []; void Init (int coords) { ArrayResize (decision, coords); fitness = -DBL_MAX; } }; // Структура журнала struct S_Journal { S_Journal_Entry entries []; int length; int maxLength; void Init (int maxLen, int coords) { maxLength = maxLen; length = 0; ArrayResize (entries, maxLen); for (int i = 0; i < maxLen; i++) { entries [i].Init (coords); entries [i].fitness = -DBL_MAX; // Инициализируем минимальным значением } } void Add (double fit, const double &coord []) { // Быстрая проверка - если хуже всех и журнал полон, не добавляем if (length >= maxLength && fit <= entries [length - 1].fitness) return; int insertPos = length; // Находим позицию для вставки (бинарный поиск) if (length > 0) { int left = 0; int right = length - 1; while (left <= right) { int mid = (left + right) / 2; if (entries [mid].fitness < fit) right = mid - 1; else left = mid + 1; } insertPos = left; } // Если вставляем в конец и журнал полон if (insertPos >= maxLength) return; // Сдвигаем элементы if (length < maxLength) length++; for (int i = length - 1; i > insertPos; i--) { entries [i].fitness = entries [i - 1].fitness; ArrayCopy (entries [i].decision, entries [i - 1].decision, 0, 0, WHOLE_ARRAY); } // Вставляем новый элемент entries [insertPos].fitness = fit; ArrayCopy (entries [insertPos].decision, coord, 0, 0, WHOLE_ARRAY); } }; // Расширенная структура исследователя struct S_Researcher { double x []; // текущая позиция double v []; // направление движения double b []; // личный лучший результат double rho []; // вероятности публикации в журналах double s; // стратегия управления средствами int m; // количество средств double f; // fitness текущей позиции double fb; // fitness лучшей позиции bool alive; // флаг активности void Init (int coords, int journalsNum) { if (ArraySize (x) != coords) { ArrayResize (x, coords); ArrayResize (v, coords); ArrayResize (b, coords); } if (ArraySize (rho) != journalsNum) { ArrayResize (rho, 0); ArrayResize (rho, journalsNum); } f = -DBL_MAX; fb = -DBL_MAX; m = 0; s = 0.5; alive = true; } };
Vamos definir a classe "C_AO_CoSO", que implementa o algoritmo de otimização "Community of Scientist Optimization" (CoSO). A classe "C_AO_CoSO" herda da classe base "C_AO" e pressupõe a existência de propriedades e métodos comuns a diferentes algoritmos de otimização.
São definidos valores padrão para vários parâmetros de controle do CoSO:
- tamanho inicial da população de "pesquisadores";
- quantidade total de "recursos" que podem ser alocados (na metáfora dos cientistas, podem ser bolsas de pesquisa, usadas em sua atividade de busca por soluções);
- quantidade de "periódicos" nos quais os pesquisadores podem publicar suas "descobertas" (melhores soluções);
- quantidade máxima de artigos ou descobertas que um "periódico" pode conter;
- parâmetro de "inércia", que controla a influência da direção anterior do movimento.
- phi1 = 1.5; - parâmetro cognitivo, que reflete a influência individual sobre o movimento do pesquisador (atração por suas próprias melhores descobertas);
- phi2 = 1.5; - parâmetro social, que determina em que medida o pesquisador se orienta pelas publicações nos periódicos;
- omegaMin = 0.2; - percentual mínimo de "outsiders";
- omegaMax = 0.5; - percentual máximo de "outsiders";
- epsilonPlus = 0.2; - passo de aumento da diversidade;
- epsilonMinus = 0.1; - passo de redução da diversidade.
Init () - método de inicialização do algoritmo. Recebe os intervalos de busca, com valores mínimos, máximos e passos para cada parâmetro, além do total de iterações "epochsP".
Moving () - método responsável pela atualização das posições dos pesquisadores no espaço de busca com base em suas "velocidades" e "direções".
Revision () - método responsável pela atualização da melhor solução global encontrada por todos os pesquisadores até o momento.
Campos privados (private): array dinâmico de estruturas "S_Researcher", em que cada elemento representa um "pesquisador" e contém informações sobre posição atual, velocidade, melhor solução encontrada, estado de atividade (alive), fitness (f) etc.; array dinâmico de estruturas "S_Journal", em que cada estrutura armazena um conjunto das melhores soluções publicadas em determinado "periódico"; percentual atual de "outsiders"; desvio padrão inicial; tamanho populacional efetivo atual, variável ao longo da execução do algoritmo; tamanho populacional máximo permitido.
struct S_GlobalReport - estrutura aninhada para armazenar informações sobre a melhor solução global: "fitness" (valor da função objetivo) e "index" (índice do pesquisador que encontrou essa solução).
S_GlobalReport globalReport [] - array para armazenar registros globais.
Métodos privados do algoritmo:
- UpdateDirection () - atualiza a direção de movimento (ou "velocidade") de um pesquisador específico com índice "idx".
- SubmitToJournal () - permite que o pesquisador com o índice especificado "publique" sua melhor solução atual em um dos "periódicos".
- AssignFunds () - método para distribuir "recursos" entre os pesquisadores. No CoSO, as bolsas de pesquisa podem influenciar o comportamento ou a capacidade de busca dos pesquisadores.
- HireResearchers () - método que cria novos pesquisadores.
- CreateOutsiders () - cria "outsiders", pesquisadores especiais que podem realizar uma busca mais agressiva ou aleatória para evitar o aprisionamento em ótimos locais.
- ComputeStdDev () - calcula o desvio padrão da população e serve como indicador da "diversidade" ou da "convergência" da população.
- UpdateOmega () - atualiza o parâmetro atual "omegaCurrent".
- SelectJournal () - seleciona um periódico para publicação com base nas probabilidades associadas ao pesquisador.
- NormalizeProbabilities () - normaliza o array de probabilidades para que sua soma seja igual a um.
- CompactPopulation () - método responsável por compactar a população e remover os pesquisadores menos eficientes, controlando seu tamanho.
//———————————————————————————————————————————————————————————————————— class C_AO_CoSO : public C_AO { public: //---------------------------------------------------------- ~C_AO_CoSO () { } C_AO_CoSO () { ao_name = "CoSO"; ao_desc = "Community of Scientist Optimization"; ao_link = "https://www.mql5.com/ru/articles/18886"; popSize = 30; // начальный размер популяции totalFunds = 150; // общее количество средств journalsNum = 3; // количество журналов journalLen = 10; // длина журнала omega = 0.7; // параметр инерции ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "totalFunds"; params [1].val = totalFunds; params [2].name = "journalsNum"; params [2].val = journalsNum; params [3].name = "journalLen"; params [3].val = journalLen; params [4].name = "omega"; params [4].val = omega; //---------------------------------------------------------------- phi1 = 1.5; // когнитивный параметр phi2 = 1.5; // социальный параметр omegaMin = 0.2; // минимальный процент аутсайдеров omegaMax = 0.5; // максимальный процент аутсайдеров epsilonPlus = 0.2; // шаг увеличения разнообразия epsilonMinus = 0.1; // шаг уменьшения разнообразия } void SetParams () { popSize = (int)params [0].val; totalFunds = (int)params [1].val; journalsNum = (int)params [2].val; journalLen = (int)params [3].val; omega = params [4].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ int totalFunds; // общее количество средств int journalsNum; // количество журналов int journalLen; // длина журнала double omega; // параметр инерции double phi1; // когнитивный параметр double phi2; // социальный параметр double omegaMin; // минимальный процент аутсайдеров double omegaMax; // максимальный процент аутсайдеров double epsilonPlus; // шаг увеличения разнообразия double epsilonMinus; // шаг уменьшения разнообразия private: //--------------------------------------------------------- S_Researcher researchers []; // массив исследователей S_Journal journals []; // массив журналов double omegaCurrent; // текущий процент аутсайдеров double sigma0; // начальное стандартное отклонение int actualPopSize; // текущий размер популяции int maxPopSize; // максимальный размер популяции double socialComponent []; // кэш для социального компонента struct S_GlobalReport { double fitness; int index; }; S_GlobalReport globalReport []; // Методы алгоритма void UpdateDirection (int idx); void SubmitToJournal (int idx); void AssignFunds (int availableFunds); void HireResearchers (int idx); void CreateOutsiders (int outsiderFunds); double ComputeStdDev (); void UpdateOmega (); int SelectJournal (const double &probs []); void NormalizeProbabilities (double &probs []); void CompactPopulation (); }; //————————————————————————————————————————————————————————————————————
O método "Init" faz parte da classe "C_AO_CoSO" e é responsável por preparar todas as estruturas e parâmetros necessários antes do início da execução do algoritmo. Primeiro, é realizada a inicialização padrão, relacionada aos intervalos dos parâmetros de busca (valores mínimos, máximos e passo), com a definição do número de iterações ("epochsP"). Se essa inicialização padrão falhar, o método retorna "false". Em seguida, são inicializadas as variáveis internas de estado do algoritmo:
- actualPopSize - tamanho atual da população de pesquisadores,
- maxPopSize - tamanho máximo permitido para a população (ou espaço de memória alocado para os pesquisadores),
- sigma0 - valor inicial do desvio padrão, que será calculado posteriormente,
- omegaCurrent - valor atual do parâmetro "omega", inicializado como a média aritmética entre "omegaMin" e "omegaMax".
Na sequência, são feitas verificações de consistência dos parâmetros de entrada:
- totalFunds - a quantidade total de "recursos" deve ser pelo menos igual ao tamanho da população; cada pesquisador deve receber certa quantidade de recursos ou bolsas de pesquisa;
- journalsNum - deve haver pelo menos um "periódico";
- journalLen - cada "periódico" deve ter tamanho mínimo de 1;
- omega (parâmetro global) - deve estar no intervalo de 0.0 a 1.0.
Após a verificação dos parâmetros, é feita uma "limpeza completa das execuções anteriores", o que significa redefinir para zero os tamanhos dos arrays dinâmicos "researchers", "journals", "globalReport" e "socialComponent", para que o algoritmo sempre comece a partir de um estado limpo. As variáveis de estado já mencionadas (actualPopSize, maxPopSize, sigma0) também são redefinidas.
Em seguida, os "periódicos" são inicializados: o array "journals" tem seu tamanho ajustado de acordo com "journalsNum". Cada periódico nesse array é inicializado com o tamanho "journalLen" e o número de coordenadas "coords".
Depois, os pesquisadores são inicializados. "maxPopSize" é definido como, no mínimo, o triplo de "popSize" (tamanho da população). Isso cria uma "reserva" para possíveis mudanças no tamanho da população, já que o algoritmo cria novos pesquisadores. Também é calculado "fundsPerResearcher", a quantidade de recursos que será alocada a cada pesquisador, dividindo-se o total de recursos pelo tamanho da população. Em seguida, o método percorre todos os pesquisadores.
Cada pesquisador é inicializado com o número de coordenadas "coords" e o número de periódicos "journalsNum". A flag "alive" é definida como "true" apenas para os primeiros "popSize" pesquisadores; os demais permanecem inativos por enquanto. Aos pesquisadores ativos é atribuída a quantidade calculada de recursos "fundsPerResearcher". Sua "estratégia de gestão de recursos" "s" é inicializada aleatoriamente. Também são inicializadas suas posições "x", suas melhores posições pessoais "b" e seus vetores de movimento "v". As posições "x" e "b" são definidas aleatoriamente no intervalo entre "rangeMin" e "rangeMax", respeitando o passo "rangeStep". Os vetores de movimento "v" são inicializados com pequenos valores aleatórios provenientes de uma distribuição normal. As probabilidades "rho" de cada periódico também são inicializadas com valores aleatórios.
Em seguida, é chamado o método "NormalizeProbabilities", que normaliza essas probabilidades. Após a inicialização de todos os pesquisadores, é calculado o desvio padrão inicial "sigma0", que caracteriza a dispersão das posições dos pesquisadores em todas as coordenadas. Se "sigma0" for igual a zero, por exemplo, se todos os pesquisadores estiverem no mesmo ponto, ele é definido como 1.0 para evitar divisão por zero. O parâmetro "omegaCurrent" é novamente definido como a média entre "omegaMin" e "omegaMax".
Ao final, as posições de todos os pesquisadores inicializados (popSize) são copiadas para o array de agentes "a". Assim, o método "Init" deixa o algoritmo totalmente preparado para a execução, inicializando todos os agentes "pesquisadores", seus parâmetros, os "periódicos" para armazenamento de resultados e também os parâmetros internos de controle do algoritmo.
//———————————————————————————————————————————————————————————————————— bool C_AO_CoSO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация переменных состояния actualPopSize = 0; maxPopSize = 0; sigma0 = 0; omegaCurrent = omegaMin + (omegaMax - omegaMin) / 2.0; // Проверка корректности параметров if (totalFunds < popSize) totalFunds = popSize; if (journalsNum < 1) journalsNum = 1; if (journalLen < 1) journalLen = 1; if (omega < 0.0) omega = 0.0; if (omega > 1.0) omega = 1.0; // Полная очистка от предыдущих запусков ArrayResize (researchers, 0); ArrayResize (journals, 0); ArrayResize (globalReport, 0); ArrayResize (socialComponent, 0); // Сброс параметров actualPopSize = 0; maxPopSize = 0; sigma0 = 0; // Инициализация журналов ArrayResize (journals, journalsNum); for (int i = 0; i < journalsNum; i++) { journals [i].Init (journalLen, coords); } // Инициализация массива исследователей с запасом maxPopSize = MathMin (popSize * 3, 300); // Ограничиваем максимальный размер ArrayResize (researchers, maxPopSize); ArrayResize (socialComponent, coords); actualPopSize = popSize; int fundsPerResearcher = totalFunds / popSize; for (int i = 0; i < maxPopSize; i++) { researchers [i].Init (coords, journalsNum); researchers [i].alive = (i < popSize); if (i < popSize) { researchers [i].m = fundsPerResearcher; researchers [i].s = u.RNDprobab (); // Инициализация позиции for (int c = 0; c < coords; c++) { researchers [i].x [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); researchers [i].x [c] = u.SeInDiSp (researchers [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); researchers [i].b [c] = researchers [i].x [c]; researchers [i].v [c] = u.GaussDistribution (0.0, -0.01, 0.01, 1); } // Инициализация вероятностей журналов for (int j = 0; j < journalsNum; j++) { researchers [i].rho [j] = u.RNDprobab (); } NormalizeProbabilities (researchers [i].rho); } } // Вычисляем начальное стандартное отклонение sigma0 = ComputeStdDev (); if (sigma0 == 0) sigma0 = 1.0; // Защита от деления на ноль omegaCurrent = omegaMin + (omegaMax - omegaMin) / 2.0; // Копируем исследователей в стандартный массив агентов for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].c, researchers [i].x, 0, 0, WHOLE_ARRAY); } return true; } //————————————————————————————————————————————————————————————————————
O método "Moving" é a parte central do ciclo iterativo do algoritmo. Ele executa uma etapa da busca pela solução ótima, modelando o comportamento dos "pesquisadores" e sua interação. Se esta for a primeira chamada após a inicialização, o método apenas define "revision" como "true" e encerra. A partir da iteração seguinte, são executadas as etapas principais do algoritmo.
Atualização do fitness dos pesquisadores. Para cada pesquisador ativo da população atual, seu valor de fitness é obtido do array geral "a", onde ficam armazenados os resultados da avaliação de fitness de todos os agentes. Em seguida, verifica-se se o fitness atual do pesquisador é melhor do que seu melhor fitness pessoal registrado anteriormente e, em caso afirmativo, "fb" é atualizado, e "b" passa a receber a posição atual "x".
Submissão de resultados aos periódicos. Cada pesquisador ativo "submete" seus resultados atuais, isto é, o fitness e a posição correntes, a um ou mais "periódicos". Os detalhes desse procedimento estão encapsulados no método "SubmitToJournal", que seleciona um periódico com base nas probabilidades "rho" do pesquisador e adiciona ali seu resultado, caso ele seja suficientemente bom.
Montagem do "globalReport" e cálculo dos recursos disponíveis. Nesta etapa, o status dos pesquisadores é reavaliado e a distribuição de recursos é preparada. Para cada pesquisador ativo, a quantidade de "recursos" (m) é reduzida em uma unidade, simbolizando os gastos da iteração atual. A quantidade total de recursos disponíveis, "availableFunds", é incrementada. Se, após esse gasto, o pesquisador ainda tiver recursos (m > 0), ele é considerado apto a continuar a busca e será incluído no "globalReport". Se os recursos se esgotarem, o pesquisador "morre" (alive = false). Forma-se o "globalReport", um array que contém o fitness e o índice apenas dos pesquisadores que permanecem ativos e ainda dispõem de recursos.
Ordenação do "globalReport". Os elementos de "globalReport" são ordenados em ordem decrescente de fitness, do melhor para o pior, usando um algoritmo simples de ordenação por bolha. Isso permite identificar rapidamente os pesquisadores mais bem-sucedidos.
Distribuição de recursos. O método "AssignFunds" é chamado para redistribuir "availableFunds" entre os pesquisadores ativos. Os pesquisadores mais bem-sucedidos, de acordo com o "globalReport", recebem mais recursos, incentivando sua permanência ativa nas iterações seguintes, enquanto os menos bem-sucedidos podem receber menos ou nada, o que pode levá-los à "morte" nas iterações seguintes.
Contratação de novos pesquisadores pelos já existentes. Pesquisadores ativos que ainda dispõem de recursos suficientes (m > 1) podem "contratar" novos pesquisadores. Esse mecanismo amplia a população ao criar novos agentes a partir de pesquisadores bem-sucedidos. Os detalhes estão no método "HireResearchers".
Atualização da direção e da posição. Para cada pesquisador ativo, é chamado o método "UpdateDirection", que calcula o novo vetor de movimento "v" do pesquisador com base em seu melhor resultado pessoal "b", no melhor resultado publicado nos periódicos, no componente social e em outros fatores do algoritmo. A posição do pesquisador, "x", é atualizada pela soma com o vetor de movimento "v". A posição é verificada para saber se ultrapassa os limites permitidos e, se necessário, é corrigida. Além disso, ela é discretizada, isto é, arredondada para o valor admissível mais próximo, de acordo com "rangeStep".
Atualização do parâmetro de diversidade. Chama-se o método "UpdateOmega", que ajusta o parâmetro "omegaCurrent" do algoritmo. Esse parâmetro é usado para controlar o equilíbrio entre exploração, isto é, a busca por novas regiões, e intensificação, isto é, o refinamento das soluções encontradas, variando dinamicamente ao longo da execução do algoritmo para manter a diversidade da população.
Compactação da população. Chama-se o método "CompactPopulation" para remover do array "researchers" os pesquisadores inativos (alive = false), reduzindo efetivamente seu tamanho e liberando memória.
Cópia das posições para o array de agentes. Por fim, as posições atuais de todos os pesquisadores ativos são copiadas para o array "a". O tamanho de "a" é atualizado de acordo com "actualPopSize". A variável global "popSize" também é atualizada para o novo valor de "actualPopSize".
Assim, o método "Moving" encapsula o ciclo completo de uma iteração do algoritmo CoSO, incluindo avaliação, interação social ("periódicos"), gestão de recursos, variação dinâmica da população e deslocamento dos agentes no espaço de busca.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::Moving () { if (!revision) { revision = true; return; } //--- Основные шаги CoSO: // 1. Обновление fitness исследователей из массива агентов int aSize = ArraySize (a); for (int i = 0, j = 0; i < actualPopSize && j < aSize; i++) { if (!researchers [i].alive) continue; researchers [i].f = a [j].f; // Обновление личного лучшего if (researchers [i].f > researchers [i].fb) { researchers [i].fb = researchers [i].f; ArrayCopy (researchers [i].b, researchers [i].x, 0, 0, WHOLE_ARRAY); } j++; } // 2. Подача результатов в журналы for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) SubmitToJournal (i); } // 3. Сбор глобального отчета и подсчет доступных средств int availableFunds = 0; int reportSize = 0; // Предварительный подсчет размера отчета for (int i = 0; i < actualPopSize; i++) { if (!researchers [i].alive) continue; researchers [i].m--; // Тратим 1 единицу средств за итерацию availableFunds++; if (researchers [i].m > 0) reportSize++; else researchers [i].alive = false; } // Заполнение глобального отчета ArrayResize (globalReport, reportSize); int idx = 0; for (int i = 0; i < actualPopSize && idx < reportSize; i++) { if (researchers [i].alive && researchers [i].m > 0) { globalReport [idx].fitness = researchers [i].f; globalReport [idx].index = i; idx++; } } // 4. Быстрая сортировка глобального отчета for (int i = 0; i < reportSize - 1; i++) { for (int j = i + 1; j < reportSize; j++) { if (globalReport [i].fitness < globalReport [j].fitness) { S_GlobalReport temp = globalReport [i]; globalReport [i] = globalReport [j]; globalReport [j] = temp; } } } // 5. Распределение средств AssignFunds (availableFunds); // 6. Найм новых исследователей существующими for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive && researchers [i].m > 1) HireResearchers (i); } // 7. Обновление направления и позиции для каждого исследователя for (int i = 0; i < actualPopSize; i++) { if (!researchers [i].alive) continue; UpdateDirection (i); // Обновление позиции for (int c = 0; c < coords; c++) { researchers [i].x [c] += researchers [i].v [c]; // Контроль границ if (researchers [i].x [c] < rangeMin [c]) researchers [i].x [c] = rangeMin [c]; if (researchers [i].x [c] > rangeMax [c]) researchers [i].x [c] = rangeMax [c]; researchers [i].x [c] = u.SeInDiSp (researchers [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } // 8. Обновление параметра разнообразия UpdateOmega (); // 9. Компактификация популяции CompactPopulation (); // 10. Копируем позиции в массив агентов для вычисления fitness ArrayResize (a, actualPopSize); idx = 0; for (int i = 0; i < maxPopSize && idx < actualPopSize; i++) { if (researchers [i].alive) { a [idx].Init (coords); ArrayCopy (a [idx].c, researchers [i].x, 0, 0, WHOLE_ARRAY); idx++; } } popSize = actualPopSize; // Обновляем размер популяции } //————————————————————————————————————————————————————————————————————
O método "UpdateDirection" é responsável por atualizar o vetor de movimento "v" de um pesquisador específico no algoritmo CoSO. Essa etapa é fundamental para o deslocamento dos agentes (pesquisadores) no espaço de busca e lhes permite explorar novas regiões, além de aproveitar as informações obtidas tanto individualmente quanto a partir de outros agentes. O método recebe um único parâmetro de entrada: "idx" (o índice do pesquisador cujo movimento deve ser atualizado).
No início do método, são geradas duas variáveis aleatórias no intervalo de 0 a 1: "beta1", usada como coeficiente do componente pessoal, e "beta2", usada como coeficiente do componente social. Em seguida, calcula-se o componente social, redefinindo o array "socialComponent" para zero, o que garante que ele esteja limpo antes de cada novo cálculo.
Depois disso, um loop percorre todos os "periódicos" disponíveis no algoritmo e, para cada periódico, verifica se ele contém registros (length > 0), já que um periódico vazio não pode fornecer informação para o componente social. Se o periódico não estiver vazio, uma entrada é escolhida aleatoriamente dele (entryIdx).
Para cada coordenada (dimensão do espaço de busca), o componente social é atualizado. A contribuição da entrada selecionada do periódico é calculada como a probabilidade de o pesquisador escolher esse periódico (rho[j]) multiplicada por (posição do periódico - posição atual do pesquisador). Essas contribuições são somadas em todos os periódicos, formando a influência total da informação social sobre o movimento do pesquisador. Após o cálculo do componente social, o vetor de movimento do pesquisador é atualizado: o novo vetor de movimento (v [c]) = componente inercial + componente pessoal + componente social.
Vamos examinar cada parte:
Componente inercial: omega - researchers [idx]. v [c]. Aqui, "omega" (o parâmetro "omegaCurrent", definido no método "Init" e atualizado em "Moving") é o coeficiente de inércia. Ele determina em que medida o pesquisador mantém sua direção anterior de movimento. Um valor alto significa que o pesquisador continuará se movendo na mesma direção; um valor baixo significa que ele mudará de direção mais rapidamente sob a influência de outros fatores.
Componente pessoal: phi1 - beta1 - (researchers [idx]. b [c] - researchers [idx]. x [c]), em que "phi1" é o coeficiente de aceleração associado à experiência pessoal, e "beta1" é um fator aleatório que introduz estocasticidade.
(researchers [idx]. b [c] - researchers [idx]. x [c]) é o vetor que aponta da posição atual do pesquisador para sua melhor posição pessoal encontrada anteriormente. Esse componente puxa o pesquisador de volta para regiões em que já obteve bons resultados.
- manter certo movimento inercial;
- retomar seus melhores resultados pessoais;
- explorar e seguir descobertas bem-sucedidas de outros pesquisadores.
Como resultado, "UpdateDirection" calcula um novo vetor de movimento para o pesquisador, que será usado na etapa seguinte para atualizar efetivamente sua posição no espaço de busca.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::UpdateDirection (int idx) { double beta1 = u.RNDprobab (); double beta2 = u.RNDprobab (); // Социальный компонент ArrayInitialize (socialComponent, 0); for (int j = 0; j < journalsNum; j++) { if (journals [j].length > 0) { int entryIdx = u.RNDminusOne (journals [j].length); for (int c = 0; c < coords; c++) { socialComponent [c] += researchers [idx].rho [j] * (journals [j].entries [entryIdx].decision [c] - researchers [idx].x [c]); } } } // Обновление направления for (int c = 0; c < coords; c++) { researchers [idx].v [c] = omega * researchers [idx].v [c] + phi1 * beta1 * (researchers [idx].b [c] - researchers [idx].x [c]) + phi2 * beta2 * socialComponent [c]; } } //————————————————————————————————————————————————————————————————————
A função "SubmitToJournal" descreve como um pesquisador publica seus resultados atuais em um dos "periódicos" disponíveis. Esse é um mecanismo fundamental para a disseminação de informações e a aprendizagem social no algoritmo CoSO. A função recebe um parâmetro: "idx", o índice do pesquisador que deseja enviar seus resultados para um periódico. A função é composta por duas etapas principais:
Escolha do periódico. Primeiro, é chamada a função auxiliar "SelectJournal". Essa função recebe como entrada o array "rho" do pesquisador. O array "rho", que representa probabilidades ou preferências, determina com que probabilidade esse pesquisador prefere submeter seus resultados a cada periódico. Com base nessas probabilidades, a função "SelectJournal" escolhe aleatoriamente um dos periódicos disponíveis e retorna seu índice (journalIdx).
Adição de entrada ao periódico. Assim que o periódico é escolhido, chama-se nele o método "Add". Esse método recebe dois parâmetros:
- researchers [idx]. f - o valor atual de fitness do pesquisador. Isso representa a qualidade da solução encontrada.
- researchers [idx]. x - a posição atual do pesquisador, isto é, as coordenadas no espaço de busca. Essa é a própria "solução" que produziu esse valor de fitness.
O método "Add" no periódico selecionado, isto é, o periódico de índice journalIdx, é responsável por efetivamente adicionar essas informações. Dessa forma, o periódico armazena o conhecimento coletivo ou as melhores práticas encontradas por diferentes pesquisadores.
Em termos gerais, "SubmitToJournal" modela o processo de publicação de resultados científicos, em que os pesquisadores escolhem para onde enviar seus trabalhos, e esses trabalhos passam a ficar disponíveis e esses trabalhos passam a ficar acessíveis a outros pesquisadores. Isso permite ao algoritmo acumular e disseminar soluções bem-sucedidas entre a população de agentes.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::SubmitToJournal (int idx) { int journalIdx = SelectJournal (researchers [idx].rho); journals [journalIdx].Add (researchers [idx].f, researchers [idx].x); } //————————————————————————————————————————————————————————————————————
A função "SelectJournal" foi projetada para selecionar um periódico dentre os disponíveis com base nas probabilidades definidas. Trata-se da implementação de uma seleção por roleta (roulette wheel selection), ou seleção proporcional, em que cada periódico tem um determinado "peso" ou "preferência". A função recebe um parâmetro: probs [] - array de números de ponto flutuante que representa as probabilidades ou preferências relativas para a escolha de cada periódico.
A função opera da seguinte forma: no início, é gerado um número aleatório "rnd", uniformemente distribuído entre 0 (inclusive) e 1 (sem incluir 1), que será usado para determinar qual periódico será escolhido. A variável "cumSum" é inicializada com zero e passa a acumular a soma das probabilidades à medida que o array "probs" é percorrido.
Tratamento do caso extremo. Se o loop terminar e nenhum periódico tiver sido selecionado, o que teoricamente pode acontecer por causa de limitações de precisão numérica, por exemplo se "rnd" for igual a 1 e a soma de todos os valores de "probs" for exatamente 1, ou se a soma de "probs" for ligeiramente menor que 1, a função retorna o índice do último periódico (probsSize - 1). Isso garante que um periódico sempre seja selecionado, mesmo em casos-limite ou patológicos.
Em essência, essa função cria uma sequência de segmentos na reta numérica de 0 a 1, em que o comprimento de cada slot é proporcional à probabilidade do periódico correspondente. Em seguida, ela lança um "dardo" (o número aleatório "rnd") e verifica em qual slot ele cai. Isso garante que periódicos com probabilidades mais altas sejam selecionados com maior frequência.
//———————————————————————————————————————————————————————————————————— int C_AO_CoSO::SelectJournal (const double &probs []) { double rnd = u.RNDprobab (); double cumSum = 0; int probsSize = ArraySize (probs); for (int i = 0; i < probsSize; i++) { cumSum += probs [i]; if (rnd <= cumSum) return i; } return probsSize - 1; } //————————————————————————————————————————————————————————————————————
Conclusão
Assim, examinamos em detalhe a teoria do algoritmo CoSO, bem como parte da implementação de seus métodos em código. O volume de conteúdo acabou sendo bem maior do que o esperado no início, e decidi dividir o artigo em duas partes. O algoritmo em si é extremamente interessante e multifacetado, com uma lógica profunda e multinível que merece uma análise cuidadosa.
Na segunda parte, continuarei a descrição dos métodos específicos, além de testar o algoritmo e apresentar as conclusões sobre sua eficiência.
Programas utilizados no artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | #C_AO.mqh | Arquivo de inclusão | Classe base dos algoritmos populacionais de otimização |
| 2 | #C_AO_enum.mqh | Arquivo de inclusão | Enumeração dos algoritmos populacionais de otimização |
| 3 | TestFunctions.mqh | Arquivo de inclusão | Biblioteca de funções de teste |
| 4 | TestStandFunctions.mqh | Arquivo de inclusão | Biblioteca de funções do ambiente de testes |
| 5 | Utilities.mqh | Arquivo de inclusão | Biblioteca de funções auxiliares |
| 6 | CalculationTestResults.mqh | Arquivo de inclusão | Script para cálculo dos resultados na tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Ambiente de testes 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_CoSO.mq5 | Script | Ambiente de testes para o CoSO |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/18886
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.
Caminhe em novos trilhos: Personalize indicadores no MQL5
Desenvolvimento do Toolkit de Análise de Price Action (Parte 16): Introduzindo a Teoria dos Quartis (II) — Intrusion Detector EA
Está chegando o novo MetaTrader 5 e MQL5
Algoritmo de Aprendizagem Competitiva
- 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