Денис Романюк. 

Идея: перебор субалгоритмов и метагенетический алгоритм.






    Предположим, перед программистом стоит задача А. Он мысленно разбивает А на подзадачи {B1, B2, ..., Bn}. Каждая или некоторые из подзадач Bx может быть решена несколькими способами. В случае, если А - задача сложная и нетривиальная, программист может попробовать следующий подход. Реализовать каждую из подзадач Вх всеми возможными способами - в виде независимых и взаимозаменяемых  классов ООП. После этого пишется цикл, в котором программист пытается решить задачу А, причем вместо В1  в цикле подставляются все возможные варианты решения  В1,  вместо В2  в цикле подставляются все возможные варианты решения  В2, ..., вместо Вn  в цикле подставляются все возможные варианты решения  Вn. В этом же цикле вычисляется наилучшее решение задачи А.

    Разумеется, необязательно использовать тривиальный перебор всех возможных вариантов. Можно применить и что-нибудь более изощренное - например, генетический алгоритм (ГА).

    Что касается задач, решаемых с помощью ГА, то перед программистм  всегда стоит проблема выбора верных параметров ГА и правильного написания важных "кусочков" ГА. Например, необходимо точно подобрать значения таких констант как количество особей в начальной популяции, вероятность мутации и т.д. Также нужно правильно запрограммировать  операторы кроссовера, мутации, методы селекции и фитнесс-функцию. Очевидно, что и значения констант, и программная реализация различных "кусочков" ГА могут быть самыми различными. Поэтому, чтобы не брать значения констант и реализацию разных частей ГА "с потолка", предлагаю следующий подход.

1. Определяются минимальное и максимальное значение каждой константы-параметра ГА.
2. В виде независимых взаимозаменяемых классов ООП программируются все возможные варианты различных "кусочков" ГА ( операторов кроссовера, мутации, методов селекции,  фитнесс-функции и т.д. )
3. В некотором внешнем алгоритме выполняется наш ГА с различными значениями констант-параметров и различными вариантами реализации операторов кроссовера, мутации, методов селекции,  фитнесс-функции и т.д. Простейшим вариантом этого внешнего алгоритма является простой цикл с перебором вариантов и поиском оптимального решения. Если этим внешним алгоритмом является некий ГА, то можно говорить о метагенетическом алгоритме. Причем может быть ГА не только второго уровня, но и третьего, четвертого и т.д. Тема для размышления: "Может ли быть такое, что ГА1 настраивает ГА2, а ГА2 настраивает ГА1?"


На главную