18.Кажаров А.А., Рокотянский А.А. "Дарвинистский подход в создании ИИ"

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

Исследования в области "искусственного интеллекта" (ИИ) к настоящему времени привели к ряду впечатляющих результатов. Именно поэтому остро стоящий в 60-е годы XX века вопрос "может ли машина мыслить?" в настоящее время не вызывает такого интереса, поскольку на ЭВМ удалось смоделировать некоторые интеллектуальные процедуры. Более того, некоторые программные продукты по результатам своей деятельности оказываются эффективнее, чем деятельность человеческого мозга. Однако успехи, достигнутые в области ИИ, не снимают с повестки дня другой вопрос, который в несколько грубой форме может быть сформулирован так: насколько адекватно с помощью "искусственного интеллекта" удается смоделировать существенные особенности работы естественного интеллекта, работу человеческого сознания? Для того чтобы снять некоторую некорректность поставленного вопроса, необходимо учесть то, что любой продукт ИИ суть не что иное, как реализация некоторой модели интеллектуальных процессов. Тогда более точная формулировка проблемы будет заключаться в вопросе о границах применимости господствующей в настоящее время в ИИ парадигмы моделирования сознания, поскольку построение модели такого сложного феномена как сознание и, тем более, ее машинная реализация связаны с неизбежными упрощениями и схематизмом. Именно этой проблематике и посвящен данный доклад.

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

Практическая необходимость решения ряда NP-полных задач в оптимизационной постановке при проектировании и исследовании сложных систем привела разработчиков алгоритмического обеспечения к использованию биологических механизмов поиска наилучших решений. В настоящее время эффективные алгоритмы разрабатываются в рамках научного направления, которое можно назвать "природные вычисления", объединяющего такие разделы, как генетические алгоритмы, эволюционное программирование, нейросетевые вычисления, клеточные автоматы и ДНК-вычисления, муравьиные алгоритмы. Исследователи обращаются к природным механизмам, которые миллионы лет обеспечивают адаптацию биоценозов к окружающей среде. Одним из таких механизмов, имеющих фундаментальный характер, является механизм наследственности. Его использование для решения задач оптимизации привета к появлению генетических алгоритмов.

Итак, основой идей современной алгоритмики послужила дарвинистский подход, концепции Поппера и Пиаже. Отличительной особенностью подобного подхода является его универсальность, применимость практически к любым задачам.

Алгоритм решения задач оптимизации, основанный на идеях наследственности в биологических популяциях, был впервые предложен Джоном Холландом (1975 г.). Он получил название репродуктивного плана Холланда, и широко использовался как базовый алгоритм в эволюционных вычислениях. Дальнейшее развитие эти идеи, как собственно и свое название - генетические алгоритмы, получили в работах Гольдберга и Де Йонга.

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

Структура данных генетического алгоритма состоит из набора хромосом.

Каждая хромосома (строка) представляет собой последовательное объединение ряда подкомпонентов, которые называются генами. Гены расположены в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями - это биологическая терминология. В представлении хромосомы бинарной строкой, ген является битом этой строки, локус есть позиция бита в строке, а аллель это значение гена, 0 или 1. Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров задачи. В генетике под мутацией понимается преобразование хромосомы, случайно изменяющее один или несколько генов. Наиболее распространенный вид мутации случайное изменение только одного из генов хромосомы. Термин кроссинговер обозначает порождение из двух хромосом двух новых путем обмена генами. В литературе по генетическим алгоритмам также употребляется термин кроссинговер, скрещивание или рекомбинация. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии. При скрещивании хромосомы разрезаются в случайной точке и обмениваются частями между собой.

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

Затем происходит отбор (с замещением) всех п особей для дальнейшей генетической обработки, согласно убыванию величины P{i). Простейший пропорциональный отбор реализуется с помощью рулетки (Гольдберг, 1989 г.). "Колесо" рулетки содержит по одному сектору для каждого члена популяции, а размер i-ого сектора пропорционален соответствующей величине P(i). При таком отборе члены популяции, обладающие более высокой приспособленностью, будут выбираться чаше по вероятности.

После отбора выбранные п особей подвергаются рекомбинации с заданной вероятностью Рс, при этом п хромосом случайным образом разбиваются на n/2 пар. Для каждой пары с вероятность Рс может быть выполнена рекомбинация. Если рекомбинация происходит, то полученные потомки заменяют собой родителей. Одноточечная рекомбинация работает следующим образом. Случайным образом выбирается одна из точек разрыва, т.е. участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этому участку. Затем соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

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

Полученное новое поколение обладает (по вероятности) более высокой приспособленностью, наследованной от "хороших" представителей предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В результате популяция будет сходиться к локально оптимальному решению задачи, а иногда, может быть, благодаря мутации, и к глобальному ОПТИМУМУ.

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