Генетическое программирование [закрыто]

Недавно я просматривал Reddit и наткнулся на сообщение, ссылающееся на пример «генетического алгоритма JavaScript». Я действительно был очарован концепциями генетических алгоритмов и программирования, однако даже после некоторого поиска в Google я все еще немного запутался. Как это работает?

Я полагаю, словарные термины сбивают меня с толку больше всего на свете. Буду признателен за краткие примеры и, возможно, объяснения. Просто концепция генетического программирования и как я мог реализовать его в своих проектах и ​​почему?

Похоже, вы говорите о генетических алгоритмах больше, чем о генетическом программировании, но вот мой вклад в ваше понимание.

Может быть удобно думать о ГА с точки зрения частей, из которых они состоят.

Допустим, у вас есть какая-то проблема. Первое, что вам нужно, это способ выразить, как будет выглядеть решение. Если у вас возникла проблема с коммивояжером в городах A, B, C, D, E, то вы уже знаете, как может выглядеть решение, массив названий городов [B, C, A, D, E].

Это ген .

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

Сейчас. Как узнать, хорошее ли решение? Вам нужна функция, которая может сообщить вам и оценить решение. Итак, опять же, в TSP у вас может быть функция, которая измеряет пройденное расстояние, используя путь [B, C, A, D, E]. «Оценкой», которую вы назначаете, может быть просто пройденное расстояние, но в более сложные задачи вы можете включить такие вещи, как стоимость поездки и другие вещи.

Это фитнес-функция .

Так что теперь вы можете принять потенциальное решение и выяснить, хорошо ли оно. Что дальше?

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

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

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

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

Получив новое поколение, вы бросаете случайную, но редкую мутацию в каждого ребенка. Я часто видел, как частота мутаций составляет менее 1%. Функция мутации случайным образом изменит что-то в вашем закодированном гене. Если ваш ген представляет собой битовую строку, он может поменяться местами, если это массив городов, он может поменять местами 2 города в списке. Важной частью является то, что это относительно редкое явление и все перемешивается.

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

Это было немного многословно, поэтому позвольте мне подвести итог с метафорой:

1. Гены - это люди: люди решают проблемы
2. Фитнес-функции - это оценки. Люди получают оценку в зависимости от того, насколько хорошо они решают проблему.
3. Вы выбираете 2 человек для разведения новой популяции: вы даете людям с лучшими оценками больше шансов на размножение
4. Когда родители размножаются, они объединяются, чтобы произвести детей.
5. Вы редко и случайно мутируете своих детей
6. Вы оцениваете детей нового населения
7. Промыть и повторить

Надеюсь это поможет.

закодировать решение проблемы как битовую строку

написать функцию (называемую «фитнес-функцией»), которая оценивает, насколько «хорошо» закодированному решению дается битовая строка - результатом обычно является число от 0 до 1

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

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

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

повторять, пока хорошее решение не развивается

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

Я настоятельно рекомендую книгу « Генетические алгоритмы в поиске, оптимизации и машинном обучении».

Генетическое программирование - это способ заставить компьютер писать программы для вас!

Не думайте о «программах», таких как MS Word, думайте о «программах» следующим образом:

function(x){ return x*2; }

Эта функция (или программа) сама по себе не имеет причин для существования. Мы ищем решения проблем. Если вам нужно найти сумму двух чисел, просто откройте калькулятор и выполните математические расчеты. Что делать, если кто-то дал вам следующую таблицу и попросил вас выяснить отношения между resultи xи y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

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

Допустим, вы не знаете статистику и решаете, что эту проблему слишком сложно решить самостоятельно, поэтому вы получите компьютер, чтобы решить ее за вас.

Пусть компьютер генерирует случайные догадки

У вас есть компьютер, который генерирует миллион ответов, и посмотрите, придерживается ли какой-либо из них (угадайте ... миллион раз!). Ниже приведен пример пары догадок:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

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

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Вы можете сделать так, чтобы оно выглядело больше как дерево, сделав отступ таким образом (кстати, посмотрите обратную польскую запись и синтаксис lisp ... но вы поймете, почему мы представляем такие программы в ближайшее время):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +находится наверху с двумя «листочками» /и y. /сама имеет несколько детей и т. д.)

Вот почему вы так много читаете о «деревьях» в генетическом программировании. В любом случае, мы вставляем значения xи yв эту функцию, и это дает нам НЕПРАВИЛЬНЫЙ ответ. Не удивительно, так как мы случайно сгенерировали это.

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

Что отличает GP?

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

Вы случайным образом выбираете два решения, случайным образом выбираете поддеревья и начинаете их менять местами. Таким образом, часть решения A попадает под решение B, и наоборот - вы просто «пересекли» их. Вы также берете некоторые решения и просто «мутируете» их ... берете какое-то поддерево и немного «облажаете» (эй, если решение ужасное, «облажаться без причины» может действительно улучшить его).

Хороший способ думать об этом заключается в следующем: у вашей мамы и папы есть определенные атрибуты - цвет волос, рост, вероятность заболевания и т. Д. Вы, будучи ребенком, наследуете разные атрибуты от обоих ваших родителей. Если оба ваших родителя были олимпийцами, вы тоже будете супер спортсменом, верно? Ну, биологи, социологи и даже историки могут не согласиться с этой идеей, но компьютерные ученые не обеспокоены моралью евгеники здесь. Они просто увидели, что «система» довольно хорошо справляется с поставками решений, поэтому они решили смоделировать ее в программном обеспечении.

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

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

Мы продолжаем это в течение очень большого числа поколений. Каждое поколение (надеюсь) предлагает лучшие и лучшие решения, пока мы не получим правильный ответ. Например:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Хорошо, посмотрите на это, это правильно!
(Я скопировал это с http://en.wikipedia.org/wiki/Genetic_programming , который также имеет графическое представление этого дерева)

Шансы и Концы

Есть несколько важных вопросов, например, как вы решаете, какие «терминалы» ( +, -, *, /, cos, sin, tan) доступны для вашей системы GP, как вы пишете фитнес-функцию и как система обрабатывает бессмысленные программы, такие как (1 + cos)или (2 / "hello")(среди многих других).

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

Я написал большую часть этого по памяти, но это основная идея. Я учился в колледже. Вы должны определенно поиграть с этим. Не беспокойтесь о понимании всей терминологии, просто скачайте несколько бесплатных GP-систем, ознакомьтесь с несколькими примерами, чтобы почувствовать это и создать свои собственные интересные примеры (найдите взаимосвязи между различными наборами данных, попробуйте подключить их к игре API и т. Д.)

Выживание наиболее приспособленных: естественный отбор с помощью Windows Forms - вот как я познакомился с генетическим программированием. Это легко прочитать с помощью кода, доступного для скачивания. Недостатком является то, что GP требует средства для выполнения кода, созданного во время выполнения, и на момент написания статьи C # не подходил для этой задачи. Вот почему в примере используется CodeDOM для генерации, компиляции и запуска кода во время выполнения, что само по себе добавляет к нему еще один уровень сложности.

С тех пор все изменилось, и теперь в .NET появился собственный API-интерфейс ExpressionTree, который, вероятно, позволил бы реализовать более элегантную реализацию GP в C #, чем та, которая описана в статье. Но этого достаточно, чтобы понять, как работает GP.

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

Генетические алгоритмы и генетическое программирование связаны между собой, но разные понятия.

Генетические алгоритмы (ГА) - это поисковые алгоритмы для сложных задач оптимизации. В GA вы кодируете параметры решения некоторой проблемы в цепочке битов «ДНК», а затем случайным образом «размножаете» эти цепочки битов: воспроизводите их путем объединения их частей и применяете «выживание наиболее приспособленных», удаляя все цепочки битов у вас есть, за исключением тех, которые являются лучшими в решении вашей проблемы.

Генетическое программирование (GP) еще более сложное: здесь вы представляете программы не по их ДНК (цепочкам битов), а по синтаксическому анализу деревьев, которые вы производите и выбираете.