GAFT — структура генетического алгоритма, реализованная на Python.

искусственный интеллект Python алгоритм API
GAFT — структура генетического алгоритма, реализованная на Python.

предисловие

В последнее время мне нужно использовать генетические алгоритмы для оптимизации некоторых вещей.Сначала я планировал реализовать простую функцию непосредственно на основе некоторых алгоритмов для оптимизации, но я чувствую, что просто написать неуниверсальную функцию для запуска более позднего улучшенного оператора или других принесет трудности.В то же время, основная концепция и процесс работы генетического алгоритма относительно фиксированы, и улучшение обычно осуществляется с помощью механизма кодирования, стратегии отбора, оператора перекрестной мутации и дизайна параметров и т. д., что не имеет большого значения. влияет на общую структуру алгоритма. Таким образом, для генетических алгоритмов очень удобно писать относительно фиксированную структуру и оставлять место для операторов, параметров и т. д. для тестирования и улучшения новых алгоритмов. Итак, я написал небольшой фреймворк генетического алгоритма, gaft. В этой статье представлены некоторые из этих фреймворков и представлены примеры использования одномерного и двумерного поиска.

GitHub: github.com/PytLab/gaft
PyPI: pypi.python.org/pypi/gaft

В настоящее время фреймворк завершил только начальную версию, которая относительно проста.Встроено несколько основных общих операторов.Пользователи могут реализовывать пользовательские операторы в соответствии с правилами интерфейса и помещать их в фреймворк для запуска. Я также добавлю больше операторов улучшения в будущем в соответствии со своими потребностями и улучшу структуру, чтобы сделать ее болееУниверсальный.

текст

Введение в генетические алгоритмы

Здесь я даю краткое введение в основные концепции генетического алгоритма и излагаю принципы проектирования Гафта.

Короче говоря, генетический алгоритм использует технологию поиска популяции, чтобы представить популяцию как возможное решение ряда проблем, и генерирует новое поколение популяции, применяя к текущей популяции ряд генетических операций, таких как отбор, скрещивание и мутация. и постепенно развивает популяцию, чтобы включить приблизительное состояние глобального оптимального решения. Ниже я суммирую соответствие между генетикой и терминами, связанными с генетическим алгоритмом:

срок

генетический термин Терминология генетического алгоритма
группа множество допустимых решений
физическое лицо Возможное решение
хромосома Кодирование возможных решений
Ген компоненты, которые можно расшифровать
генная форма генетический код
приспособляемость Значение функции оценки
выберите выберите действие
Пересекать кроссовер
Мутации операция мутации

Особенности алгоритма

  1. Использование кодирования переменных решения в качестве объекта операции позволяет процессу оптимизации заимствовать концепции из биологии.
  2. Непосредственно используйте целевую функцию, так как информация о поиске для определения направления поиска очень широка, что является оптимизацией без производных.
  3. Использование поисковой информации нескольких точек поиска одновременно является неявным параллелизмом.
  4. метод вероятностного поиска
  5. Обладает характеристиками самоорганизации, самоадаптации и самообучения.

Поток алгоритма

Гафт принципы дизайна

Поскольку процесс генетического алгоритма относительно фиксирован, наш алгоритм оптимизации в основном изменяет механизм кодирования, операторы, параметры и т. д. в рамках общей структуры процесса.Поэтому при написании структуры я хочу адаптировать эти фиксированные генетические операторы к адаптироваться к Функция степени написана как интерфейс, а метаклассы, декораторы и т. д. используются для реализации ограничений и оптимизаций интерфейса, что облегчает последующую настройку пользовательских операторов и фитнес-функций. Наконец, различные части объединяются вместе, чтобы сформировать механизм, а затем генетический алгоритм запускается в соответствии с потоком алгоритма для оптимизации цели.

Таким образом, мы можем избавиться от громоздкого процесса написания генетического алгоритма каждый раз, каждый раз, когда нам нужно только реализовать свой собственный оператор и фитнес-функцию, например, написать плагин, мы можем положить его в gaft и начать тестировать. алгоритм или оптимизировать целевую функцию.

Структура файла GAFT

В этой части я представлю общую структуру фреймворка, который я реализовал.

.
├── LICENSE
├── MANIFEST.in
├── README.rst
├── examples
│   ├── ex01
│   └── ex02
├── gaft
│   ├── __init__.py
│   ├── __pycache__
│   ├── analysis
│   ├── components
│   ├── engine.py
│   ├── operators
│   └── plugin_interfaces
├── setup.cfg
├── setup.py
└── tests
    ├── flip_bit_mutation_test.py
        ├── gaft_test.py
        ├── individual_test.py
        ├── population_test.py
        ├── roulette_wheel_selection_test.py
        └── uniform_crossover_test.py

Результаты текущего файла, как показано выше,

  • /gaft/componentsВстроенные индивидуальные и популяционные типы определены в , а также предусмотрены два различных генетических кодирования: двоичное кодирование и реальное кодирование.
  • /gaft/plugin_interfacesСередина — определение интерфейса плагина, в нем находятся все определения операторов и правила интерфейса анализа «на лету», пользователи могут писать свои плагины и вставлять их в движок в соответствии с этим.
  • /gaft/operatorsЕсть встроенные генетические операторы, они тоже следуют/gaft/plugin_interfacesЕго можно использовать как пример написания операторов. Среди операторов в настоящее время у меня есть встроенный оператор выбора колеса рулетки, оператор универсального кроссовера и оператор мутации флипбита. Пользователи могут напрямую использовать встроенные операторы, чтобы использовать gaft для оптимизации своих собственных задач.
  • /gaft/analysisЕсть встроенный плагин для оперативного анализа, который может анализировать переменные в итеративном процессе генетического алгоритма.Например, у меня есть встроенный консольный вывод информации журнала, и сохранение итеративных значений пригодности и т. д. Плагин облегчает построение кривых эволюции.
  • /gaft/engineЭто модуль управления процессом генетического алгоритма, который объединяет все ранее определенные части вместе, чтобы использовать процесс генетического алгоритма для итерации оптимизации.

Использовать ГАФТ

Ниже я буду использовать две функции в качестве примера использования GAFT для оптимизации целевой функции.

одномерный поиск

Сначала оптимизируем простую функцию с несколькими локальными экстремумами, воспользуемся встроенным оператором, чтобы найти функцию
?
f(x) = x + 10sin(5x) + 7cos(4x)
?
Максимальное значение , диапазон значений x $[0, 10]$

  1. Сначала импортируйте необходимые модули

     from math import sin, cos

 # 导入种群和内置算子相关类
 from gaft import GAEngine
 from gaft.components import GAIndividual
 from gaft.components import GAPopulation
 from gaft.operators import RouletteWheelSelection
 from gaft.operators import UniformCrossover
 from gaft.operators import FlipBitMutation

 # 用于编写分析插件的接口类
 from gaft.plugin_interfaces.analysis import OnTheFlyAnalysis

 # 内置的存档适应度函数的分析类
 from gaft.analysis.fitness_store import FitnessStoreAnalysis

 # 我们将用两种方式将分析插件注册到遗传算法引擎中

  2. Создать движок

     # 定义种群
 indv_template = GAIndividual(ranges=[(0, 10)], encoding='binary', eps=0.001)
 population = GAPopulation(indv_template=indv_template, size=50)

 # 创建遗传算子
 selection = RouletteWheelSelection()
 crossover = UniformCrossover(pc=0.8, pe=0.5)
 mutation = FlipBitMutation(pm=0.1)

 # 创建遗传算法引擎, 分析插件和适应度函数可以以参数的形式传入引擎中
 engine = GAEngine(population=population, selection=selection,
                   crossover=crossover, mutation=mutation,
                   analysis=[FitnessStoreAnalysis])

  3. индивидуальная фитнес-функция

    Фитнес-функцию можно зарегистрировать в движке с помощью модификаторов.

     @engine.fitness_register
 def fitness(indv):
     x, = indv.variants
     return x + 10*sin(5*x) + 7*cos(4*x)

  4. Пользовательский плагин для оперативного анализа

    Вы также можете напрямую зарегистрировать плагин в движке через модификатор, когда он определен

     @engine.analysis_register
 class ConsoleOutputAnalysis(OnTheFlyAnalysis):
     interval = 1

     def register_step(self, ng, population, engine):
         best_indv = population.best_indv(engine.fitness)
         msg = 'Generation: {}, best fitness: {:.3f}'.format(ng, engine.fitness(best_indv))
         engine.logger.info(msg)

     def finalize(self, population, engine):
         best_indv = population.best_indv(engine.fitness)
         x = best_indv.variants
         y = engine.fitness(best_indv)
         msg = 'Optimal solution: ({}, {})'.format(x, y)
         engine.logger.info(msg)

  5. Хорошо, запускаем (оптимизацию)!

    У нас тут популяция из 100 поколений.

     if '__main__' == __name__:
     # Run the GA engine.
     engine.run(ng=100)

Встроенный модуль анализа будет записывать оптимальных особей каждого поколения в каждой итерации и генерировать данные для сохранения.

Постройте кривую самой функции и кривую эволюции, которую мы получили с помощью генетического алгоритма:

Анимация процесса оптимизации:

2D-поиск

Далее мы используем встроенный оператор GAFT для поиска бинарной функции, которая также имеет несколько крайних точек.
?
f(x) = ysin(2\pi x) + xcos(2\pi y)
?

Максимальное значение , диапазон значений x, y равен $[-2, 2]$.

Здесь мы не настраиваем плагин анализа, а напрямую используем встроенный класс анализа и напрямую передаем его при построении движка.

'''
Find the global maximum for binary function: f(x) = y*sim(2*pi*x) + x*cos(2*pi*y)
'''

from math import sin, cos, pi

from gaft import GAEngine
from gaft.components import GAIndividual
from gaft.components import GAPopulation
from gaft.operators import RouletteWheelSelection
from gaft.operators import UniformCrossover
from gaft.operators import FlipBitMutation

# Built-in best fitness analysis.
from gaft.analysis.fitness_store import FitnessStoreAnalysis
from gaft.analysis.console_output import ConsoleOutputAnalysis

# Define population.
indv_template = GAIndividual(ranges=[(-2, 2), (-2, 2)], encoding='binary', eps=0.001)
population = GAPopulation(indv_template=indv_template, size=50)

# Create genetic operators.
selection = RouletteWheelSelection()
crossover = UniformCrossover(pc=0.8, pe=0.5)
mutation = FlipBitMutation(pm=0.1)

# Create genetic algorithm engine.
# Here we pass all built-in analysis to engine constructor.
engine = GAEngine(population=population, selection=selection,
                  crossover=crossover, mutation=mutation,
                  analysis=[ConsoleOutputAnalysis, FitnessStoreAnalysis])

# Define fitness function.
@engine.fitness_register
def fitness(indv):
    x, y = indv.variants
    return y*sin(2*pi*x) + x*cos(2*pi*y)

if '__main__' == __name__:
    engine.run(ng=100)

Кривая эволюции:

2D функциональная поверхность:

Анимация процесса поиска:

Видно, что текущие встроенные базовые операторы вполне могут найти оптимальную точку функции в примере.

Суммировать

В этой статье в основном представлена ​​разработанная мной платформа Python для расчета оптимизации с помощью генетического алгоритма, которая имеет встроенные компоненты, обычно используемые в генетических алгоритмах, включая индивидуумов, популяции и генетические операторы с различными методами кодирования. В то же время платформа также предоставляет интерфейсы для пользовательских генетических операторов и подключаемых модулей анализа, которые могут легко и быстро создавать процесс генетического алгоритма и использовать его для тестирования алгоритма.

В настоящее время фреймворк находится только на предварительной стадии, в дальнейшем в процессе его использования будут постепенно улучшаться дополнительные встроенные операторы, делая фреймворк более универсальным. Исходный код обоих примеров оптимизации в этой статье можно найти на GitHub (GitHub.com/pgirllab/GA ft…)

Текущие планы: 1. Добавить больше встроенных операторов 2. Добавить бэкэнд C++ для встроенных операторов и компонентов 3. Распараллелить

Ссылаться на

  • «Алгоритмы интеллектуальной оптимизации и примеры MATLAB»
  • "Расчет оптимизации MATLAB"
Категории