Budowa algorytmu ewolucyjnego: reprezentacja, operatory, parametry

Designing an evolutionary algorithm: representation, operators and parameters · id evodesign · aliases: EA design, evolutionary algorithm components, genetic operators, operatory genetyczne, projektowanie algorytmu ewolucyjnego

Komponenty algorytmu ewolucyjnego: reprezentacja, inicjalizacja, selekcja rodziców i przeżycia, operatory zmienności, obsługa ograniczeń, sterowanie parametrami i rzetelne porównania.

Components of an evolutionary algorithm: representation, initialisation, parent and survivor selection, variation operators, constraint handling, parameter control and sound comparison.

In one sentence

Zestaw klocków, z których składa się każdy algorytm ewolucyjny: jak zapisać rozwiązanie, kogo wybrać na rodzica i jak tworzyć potomstwo.

The building blocks of every evolutionary algorithm: how to write down a solution, whom to pick as parents and how to make offspring.

Problem it solves

Gotowy algorytm z biblioteki często nie pasuje do problemu, a zmiana jednej części potrafi zepsuć całe przeszukiwanie.

An off-the-shelf algorithm often does not fit the problem, and changing one part can break the whole search.

What it does

Działa jak przepis kucharski rozpisany na etapy: wymieniasz jeden składnik, a resztę zostawiasz, i widzisz, co zmieniło smak.

It works like a recipe split into steps: you swap one ingredient, keep the rest, and see what changed the taste.

Everyday example

Planista tras dostaw zamienia losową mutację na zamianę dwóch przystanków miejscami i nagle dostaje krótsze trasy w tym samym czasie.

A delivery route planner replaces random mutation with swapping two stops and suddenly gets shorter routes in the same time.

This concerns you if you…

• piszesz własny algorytm ewolucyjny od zera
• gotowy solver utyka na twoim problemie
• chcesz rozumieć, co robią ustawienia w bibliotece
• are writing your own evolutionary algorithm from scratch
• an off-the-shelf solver gets stuck on your problem
• want to understand what library settings actually do

Subtopics

• Krzyżowanie: łączenie cech dwóch rodziców (Crossover (recombination) operators): Recombination operators building offspring from several parents' material, chosen to fit the representation: binary, real-valued or permutation.
• Mutacja: drobne losowe zmiany rozwiązania (Mutation operators): Unary variation operators adding random perturbations to an individual; they provide exploration and reachability of the whole space.
• Nisze i utrzymywanie różnorodności populacji (Niching and diversity preservation): Diversity-preserving techniques that let population-based metaheuristics locate multiple optima of a multimodal function in a single run.
• Obsługa ograniczeń w algorytmach ewolucyjnych (kary, naprawa) (Constraint handling in evolutionary algorithms): Techniques for steering evolutionary search in constrained spaces: penalties, repair, feasibility rules, special operators and multi-objective formulations.
• Reprezentacja osobnika (kodowanie binarne, liczbowe, permutacje, drzewa) (Solution representation in evolutionary algorithms): The genotype–phenotype mapping: choosing a data structure for candidates that defines the search space and admissible operators.
• Rzetelne porównywanie algorytmów optymalizacji (benchmarki) (Benchmarking evolutionary and black-box optimisers): Methodology for comparing black-box optimisers: standardised function suites, evaluation budgets, time-to-target measures and statistical tests.
  • Krytyka „nowych” metaheurystyk opartych na metaforach (Critique of metaphor-based metaheuristics): A methodological strand showing many metaphor-based metaheuristics are renamed known techniques, and calling for description in standard optimisation terms.
• Selekcja rodziców i przeżycia (turniej, ruletka, elitaryzm) (Parent and survivor selection (tournament, roulette, elitism)): Mechanisms for choosing parents and survivors that control selection pressure: proportional, rank-based and tournament, plus replacement strategies and elitism.
• Strojenie i samoadaptacja parametrów algorytmu ewolucyjnego (Parameter tuning and control in evolutionary algorithms): Parameter tuning (static choice before a run) and parameter control (deterministic, adaptive or self-adaptive changes during a run).

Sources

• Introduction to Evolutionary Computing (2nd ed.) · A. E. Eiben, J. E. Smith
• pymoo: Multi-objective Optimization in Python · Julian Blank, Kalyanmoy Deb