Тестирование многоуровневых систем оптимизации

Тестирование многоуровневых систем оптимизации

План статьи:

1) Базовое направление исследований. Принципы тестирования МГА системы.

2) Общая схема создания и тестирования самопрограммируемых и самоотлаживающихся систем.

3) Принципы многоуровневой оптимизации.

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

Базовое направление исследований. Принципы тестирования  МГА системы

 В качестве базового теста, МГА системе необходимо будет справиться с набором задач. Например: автоматическое составление программы по открытию поля в «сапёре», поиску пути на местности с препятствиями, игре в Арканойд, диггер, тетрис. Системе МГА надо будет составить алгоритмы (программы) решения этих задач, как при наличии неполных данных о задаче, так и при отсутствии (в идеале каких бы то ни было) данных о задаче.

 Базовой фитнесс функцией (функция приспособленности, термин ГА) для отыскания оптимальных алгоритмов будет функция, определяющая максимально эфективное прохождение игры (максимальный процент полей, открытых в сапёре; максимальное число очков в арканойде, диггере, тетрисе). В дальнейшем она может модифицироваться, генетическим алгоритмом верхнего уровня в соответствии с «принципами многоуровневой оптимизации», рассмотренными далее по тексту. Принципиальным моментом, определяющим успешность опыта, будет ускорение работы генетического алгоритма за счёт оптимизации его другим генетическим алгоритмом. Поэтому ключевым вопросом является организация работы второго и третьего уровней МГА системы. Задачей этих уровней будет минимизация суммарной популяции для генетических алгоритмов нижнего уровня, что автоматически определяет фитнесс функцию верхних уровней. Дело в том что каждая особь популяции будет запускаться автоматически в соответствующей игре для определения её эффективности (фитнесс функции особи), что требует существенных вычислительных затрат. На начальном этапе необходимо определить, по каким параметрам необходимо оптимизировать генетический алгоритм, чтобы достичь максимального ускорения его работы. Предположительно одним из наиболее эффективных методов ускорения будет оптимизация по особям начальной популяции, открывающая возможности обучения от простого к сложному, свойственные естественному интеллекту. Перспективно проводить подобные исследования также от простого к сложному, то есть, начинать с варианта, когда в начальной популяции есть уже почти готовые программы, и заканчивая популяцией с полным отсутствием полезных свойств. В части «принципы многоуровневой оптимизации» более подробно рассмотрены возможные методы оптимизации генетических алгоритмов.

Цели: получение эффективного ген. алгоритма первого уровня (а в дальнейшем и последующих уровней) для решения таких задач и изучения эффективности его применения при решении задач другого типа. Второй, третий и т.д. уровни необходимы для наработки «методологии», то есть получения полезной информации и навыков для составления конечных алгоритмов и оптимизации генетических алгоритмов нижнего уровня. Изучение эффективности и универсальности полученной таким образом «методологии» и составляет основу для интерпретации результатов опыта. На этом этапе важно найти МГА систему с самыми общими исходными посылками. Работа этой системы, тем не менее, должна давать эффективные алгоритмы для решения практически любых задач.

Общая схема создания и тестирования самопрограммируемых и самоотлаживающихся систем

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

Компоненты:

1) Информационная среда,  представляющая собой совокупность закономерностей, известных для некоторой предметной области, плюс набор характерных элементов и объектов с известными свойствами, являющихся принятыми моделями объектов предметной области. 

2) Внутри этой системы работают наборы алгоритмов, осуществляющих те или иные цели в информационной среде. Для работы с этими наборами требуется третий компонент опыта.

3) Система из двух трёх уровней генетических алгоритмов последовательно, или одновременно оптимизирующих друг друга.

Планируемые результаты работы схемы: а) Создание эффективных программ (алгоритмов) выполняющих те, или иные задачи в информационной среде. 

б) Создание систем (программных комплексов) из одного двух уровней оптимизированных генетических алгоритмов и набора эффективных программ для успешной и быстрой модификации  решений при изменении исходных целей, или параметров информационной среды, или появлении дополнительных условий и т. д. и т. п.

в) Исследование полученных решений на предмет их структуры и границ применимости. Проверка тезиса о расширении границ применимости при увеличении числа уровней МГА.

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

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

Принципы многоуровневой оптимизации

О том, что можно получить из генетического алгоритма оптимизируемого другим генетическим алгоритмом при оптимизации по его различным параметрам (частям).

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

Пример1 :

В этом случае к исходному функционалу (фитнесс функции) можно добавлять функционалы произвольного вида. Например для задачи отыскания пути к месту назначения через местность с препятствиями. Если исходным функционалом является расстояние до конечной цели, то к нему можно добавить минимальное (за время движения) расстояние до какой-либо узловой точки (узкого места: мост, тоннель). Минимизируя суммарный функционал, генетический алгоритм имеет возможность сначала найти путь к узловому месту, а затем из популяции программ движения проходящих через узловое место ему будет проще скомбинировать программу доезжающую до конечной цели.

Пример2: задача достать предмет из накрытого крышкой ящика очевидным образом распадается на две подзадачи: снять крышку и достать предмет. Если задачи схожие с указанными подзадачами уже решались МГА системой, то ей довольно быстро удастся найти и скомбинировать удачный вариант действий.

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

III) Оптимизация по моделям кроссинговера генетического алгоритма нижнего уровня. По сути, подобная оптимизация служит основой создания мощнейших механизмов, на которых базируется творческое мышление, таких как комбинирование теорий и поиск аналогий в других областях знаний. Оптимизирующий функционал верхнего уровня тот же, что в примере I, за счет чего автоматом отсеиваются случаи бесполезного кроссинговера (т. е. не содержательного комбинирования теорий). 

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

IV) Оптимизация по типам и параметрам, а также частоте мутаций генетического алгоритма нижнего уровня. Оптимизация по мутациям, их типам и частоте, а также комбинирование мутаций, могут стать основой механизма появления новых экстраординарных идей и подходов. Оптимизирующий функционал верхнего уровня тот же, что в примере I. В качестве базовых можно взять мутации аналогичные имеющимся в реальной ДНК: делеции, дупликации, вставки. Однако, за счёт комбинирования мутаций, из этого базового набора можно создавать сколь угодно сложные и специализированные преобразования текста.

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

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

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