Генетические алгоритмы (GA) и генетическое программирование ( GP) - интересные области исследований.
Я хотел бы узнать о конкретных проблемах, которые вы решили использовать с помощью GA/GP, и о том, какие библиотеки/фреймворки вы использовали, если вы не сделали свой собственный.
Вопросы:
Я ищу опыт из первых рук, поэтому, пожалуйста, не отвечайте, если у вас это есть.
Не домашнее задание.
Моя первая работа в качестве профессионального программиста (1995) заключалась в создании автоматической торговой системы на основе генетического алгоритма для фьючерсов S & P500. Приложение было написано на Visual Basic 3 [!], И я понятия не имею, как я тогда что-то сделал, поскольку у VB3 даже не было классов.
Приложение начиналось с совокупности произвольно сформированных строк фиксированной длины (часть "ген" ), каждая из которых соответствовала определенной форме в поминутных ценовых данных фьючерсов S & P500, поскольку а также конкретный порядок (покупка или продажа) и стоп-лосс и стоп-прибыль. Каждая строка (или "ген" ) имела свою прибыль, оцениваемую с помощью трехлетних исторических данных; всякий раз, когда указанная "форма" соответствует историческим данным, я принял соответствующий заказ на покупку или продажу и оценил результат торговли. Я добавил оговорку, что каждый ген начинается с фиксированной суммы денег и, следовательно, потенциально может сломаться и полностью удаляться из генофонда.
После каждой оценки популяции выжившие были перекрестно размножены случайным образом (просто смешивая биты от двух родителей), причем вероятность того, что ген будет выбран в качестве родителя, будет пропорционален полученной им прибыли. Я также добавил возможность точечных мутаций, чтобы немного оживить ситуацию. После нескольких сотен поколений я попал в популяцию генов, которые могли бы превратить 5000 долларов в среднем около 10000 долларов без шансов на смерть/брокерство (по историческим данным, конечно).
К сожалению, у меня никогда не было возможности использовать эту систему вживую, так как мой босс потерял около 100 000 долларов США менее чем за 3 месяца, торгуя традиционным способом, и он потерял готовность продолжить проект. Оглядываясь назад, я думаю, что система принесла бы огромную прибыль - не потому, что я делал все правильно, а потому, что популяция генов, которые я производила, была смещена в сторону заказов на покупку (в отличие от заказов на продажу) примерно на 5: 1. И, как мы знаем с 20/20 задним числом, рынок немного вырос после 1995 года.
Я сделал немного тварей, которые жили в этом маленьком мире. У них был мозг нейронной сети, который получил некоторые результаты от мира, а выход был вектором для движения среди других действий. Их мозги были "генами".
Программа начиналась со случайной совокупности тварей со случайными мозгами. Входы и выходные нейроны были статическими, но то, что было между ними, не было.
В окружающей среде содержатся продукты питания и опасности. Пища увеличивала энергию, и когда у вас достаточно энергии, вы можете спариваться. Опасности уменьшали бы энергию, и если бы энергия была 0, они погибли.
В конечном итоге существа эволюционировали, чтобы передвигаться по миру и находить пищу и избегать опасностей.
Затем я решил сделать небольшой эксперимент. Я дал мозгу существа выходной нейрон под названием "рот" и входной нейрон, называемый "ухом". Начались и были удивлены, обнаружив, что они эволюционировали, чтобы максимизировать пространство, и каждое соответствующее существо оставалось в его соответствующей части (еда была помещена случайным образом). Они научились сотрудничать друг с другом и не вступать друг в друга. Всегда были исключения.
Тогда я попробовал что-то интересное. Я мертвые существа стали пищей. Попытайтесь угадать, что произошло! Развивались два типа существ: те, которые атаковали, как в роях, и те, которые были высоким избеганием.
Итак, какой урок здесь? Связь означает сотрудничество. Как только вы вводите элемент, где больно другое означает, что вы что-то получаете, сотрудничество разрушается.
Интересно, как это отражается на системе свободных рынков и капитализма. Я имею в виду, что если компании могут навредить своей конкуренции и убежать с ней, то ясно, что они сделают все, что в их силах, чтобы повредить конкуренцию.
Изменить:
Я написал его на С++, не используя никаких фреймворков. Написал мою собственную нейронную сеть и код GA. Эрик, спасибо, что это правдоподобно. Люди обычно не верят в полномочия GA (хотя ограничения очевидны), пока они не сыграют с ним. GA прост, но не упрощен.
Для сомневающихся нейронных сетей было доказано, что они могут имитировать любую функцию, если у них более одного слоя. GA - довольно простой способ навигации по пространству решений, находящему локальный и потенциально глобальный минимум. Объедините GA с нейронными сетями, и у вас есть довольно хороший способ найти функции, которые находят приблизительные решения для общих проблем. Поскольку мы используем нейронные сети, то мы оптимизируем функцию для некоторых входов, а не какие-то входы в функцию, поскольку другие используют GA
Вот демо-код для примера выживания: http://www.mempko.com/darcs/neural/demos/eaters/ Инструкции по сборке:
darcs clone --lazy http://www.mempko.com/darcs/neural/cd neuralcmake .makecd demos/eaters./eaters 
Я использовал GA для оптимизации посадочных мест на моем свадебном приеме. 80 гостей старше 10 столов. Функция оценки основывалась на том, чтобы держать людей с их датами, совмещать людей с чем-то общим и удерживать людей с противоположными взглядами в отдельных таблицах.
Я запускал его несколько раз. Каждый раз я получал девять хороших столов и один со всеми нечетными шарами. В конце концов, моя жена выполнила задания на места.
Мой оптимизатор коммивояжеров использовал новое отображение хромосомы в маршрут, что делало его тривиальным для размножения и мутации хромосом без риска создания недействительных туров.
Обновить: потому что пара людей спрашивала, как...
Начните с множества гостей (или городов) в произвольном, но непротиворечивом порядке, например, в алфавитном порядке. Назовите это ссылочным решением. Подумайте о гостевом указателе как номере его места.
Вместо того, чтобы пытаться кодировать это упорядочение непосредственно в хромосоме, мы кодируем инструкции для преобразования эталонного решения в новое решение. В частности, мы обрабатываем хромосомы как списки индексов в массиве для обмена. Чтобы получить декодирование хромосомы, мы начинаем с эталонного решения и применяем все свопы, обозначенные хромосомой. Перестановка двух записей в массиве всегда приводит к действительному решению: каждый гость (или город) все равно появляется ровно один раз.
Таким образом, хромосомы могут быть случайным образом сгенерированы, мутированы и скрещены с другими и будут всегда давать правильное решение.
В январе 2004 года с нами связались с Philips New Display Technologies, которые создавали электронику для первых коммерческих электронных чернил Sony Librie, которые были выпущены только в Японии за несколько лет до Amazon Kindle, а другие рынок в США и Европе.
У инженеров Philips была серьезная проблема. За несколько месяцев до того, как продукт должен был выйти на рынок, на смену страниц они все еще становились ореолом на экране. Проблема заключалась в 200 драйверах, которые создавали электростатическое поле. У каждого из этих драйверов было определенное напряжение, которое должно было быть установлено между нулем и 1000 мВ или что-то вроде этого. Но если вы измените один из них, это изменит все.
Так что оптимизация каждого напряжения драйвера индивидуально не могла быть и речи. Количество возможных комбинаций значений было в миллиардах, и для специальной камеры потребовалось около 1 минуты для оценки одной комбинации. Инженеры пробовали много стандартных методов оптимизации, но ничто не приблизилось бы.
Главный инженер связался со мной, потому что ранее я выпустил библиотеку генетического программирования для сообщества с открытым исходным кодом. Он спросил, поможет ли GP/GA, и если бы я мог участвовать. Я сделал, и около месяца мы работали вместе, меня писали и настраивали библиотеку GA, синтетические данные и его интеграцию в свою систему. Затем, в один уик-энд, они позволили ему жить вживую с настоящей вещью.
В следующий понедельник я получил эти светящиеся письма от него и их дизайнера оборудования, о том, как никто не мог поверить в удивительные результаты, обнаруженные Джорджем. Это было. Позже в этом году продукт вышел на рынок.
Мне не заплатили за него ни цента, но я получил "хвастовство". С самого начала они сказали, что они уже превысили бюджет, поэтому я знал, что было до того, как я начал работать над этим. И это отличная история для приложений GA.:)
Я использовал генетические алгоритмы (а также некоторые связанные с ними методы), чтобы определить наилучшие настройки для системы управления рисками, которая пыталась удержать золотодобытчиков от использования украденных кредитных карт для оплаты ММО. Система будет принимать несколько тысяч транзакций с "известными" значениями (мошенничество или нет) и выяснить, какая наилучшая комбинация настроек должна была правильно идентифицировать мошеннические транзакции, не имея слишком много ложных срабатываний.
У нас были данные по нескольким дюжинам (булевым) характеристикам транзакции, каждому из которых было присвоено значение и суммировано. Если сумма была выше порога, транзакция была мошенничеством. GA создаст большое количество случайных наборов значений, оценит их против совокупности известных данных, выберет те, которые набрали наилучшее (как при обнаружении мошенничества, так и при ограничении числа ложных срабатываний), а затем скрестить породы лучших каждое поколение для производства нового поколения кандидатов. После определенного количества поколений лучшим победителем был признан лучший набор значений.
Создание корпуса известных данных для проверки было ахиллесовой пятой системы. Если вы ждали возвратных платежей, вы были на несколько месяцев отстали, когда пытались ответить на мошенников, поэтому кому-то пришлось вручную просмотреть большое количество транзакций, чтобы создать этот корпус данных, не дожидаясь слишком долго.
Это привело к выявлению подавляющего большинства мошенничества, которое появилось, но не могло получить его менее 1% от большинства подверженных мошенничеству элементов (учитывая, что 90% входящих транзакций могут быть мошенничеством, что было довольно а).
Я сделал все это, используя perl. Один запуск программного обеспечения на довольно старой linux-коробке займет 1-2 часа (20 минут для загрузки данных по каналу WAN, остальное время, проведенное хрустом). Размер любого данного поколения был ограничен доступной оперативной памятью. Я буду запускать его снова и снова с небольшими изменениями параметров, ища особенно хороший набор результатов.
В целом, он избегал некоторых из gaffes, которые приходили вручную, пытаясь настроить относительные значения десятков индикаторов мошенничества и последовательно предлагали лучшие решения, чем я мог бы создать вручную. AFAIK, он все еще используется (около 3 лет после того, как я его написал).
Как и некоторые общие проблемы, такие как Traveling Salesman и вариант программа Roger Alsing Mona Lisa, я также написал эволюционный решатель Sudoku (что требовало немного более оригинальной мысли с моей стороны, а не просто повторной реализации идеи другого). Существуют более надежные алгоритмы решения Sudokus, но эволюционный подход работает достаточно хорошо.
В последние дни я играл с эволюционной программой, чтобы найти "холодные колоды" для покера, увидев эту статью Reddit. В настоящий момент это не совсем удовлетворительно, но я думаю, что смогу улучшить его.
У меня мои собственные рамки, которые я использую для эволюционных алгоритмов.
Футбол. Я построил систему GA, чтобы предсказать результат игры в неделю в AFL (Aussie Rules Football).
Несколько лет назад мне стало скучно от стандартного рабочего футбольного пула, все просто выходили в интернет и брали выбор у какого-то эксперта в прессе. Итак, я подумал, что не может быть слишком сложно победить кучу вещательных журналистов, верно? Моя первая мысль заключалась в том, чтобы принять результаты Оценки Massey, а затем показать в конце сезона мою стратегию после победы в славе и славе. Однако по причинам, которые я никогда не обнаружил, Massey не отслеживает AFL. Циник во мне полагает, что это связано с тем, что результат каждой игры AFL в основном становится случайным, но мои жалобы на недавние изменения правил принадлежат к другому форуму.
Система в основном считала наступательную силу, оборонительную силу, преимущество в полевых условиях, улучшение недели (или ее отсутствие) и скорость изменений к каждому из них. Это создало набор полиномиальных уравнений для каждой команды за сезон. Победитель и оценка для каждого матча за заданную дату могут быть рассчитаны. Цель заключалась в том, чтобы найти набор коэффициентов, которые наиболее точно соответствовали результатам всех прошлых игр и использовали их для прогнозирования предстоящей недели.
На практике система найдет решения, которые точно предсказали бы более 90% результатов прошлой игры. Тогда он успешно заберет около 60-80% игр на предстоящую неделю (то есть неделю не в учебном наборе).
Результат: чуть выше середины пакета. Никакой основной денежный приз и система, которую я мог бы использовать, чтобы победить Вегас. Было весело, хотя.
Я построил все с нуля, без использования рамки.
Я разработал домашний brew GA для трехмерной системы лазерных профилей, разработанный моей компанией для грузовой отрасли еще в 1992 году. Система опиралась на трехмерную триангуляцию и использовала пользовательский лазерный сканер, камеру 512x512 (с пользовательским захватом hw). Расстояние между камерой и лазером никогда не было точным, и фокальная точка камеры не была найдена в 256 256 позиции, которую вы ожидали!
Это был кошмар, чтобы попытаться выработать параметры калибровки, используя стандартную геометрию и моделируемое решение уравнения стиля отжига.
Генетический алгоритм был взят вечером, и я создал калибровочный куб, чтобы проверить его. Я знал размеры куба с высокой точностью, и поэтому идея заключалась в том, что моя GA могла разработать набор пользовательских параметров триангуляции для каждой единицы сканирования, которая позволила бы преодолеть производственные вариации.
Трюк сработал. Я был ошеломлен, если не сказать больше! Внутри 10 поколений мой "виртуальный" куб (созданный из необработанного сканирования и воссозданный по параметрам калибровки) на самом деле выглядел как куб! После примерно 50 поколений мне понадобилась калибровка.
Часто бывает сложно получить точную комбинацию цветов, когда вы планируете рисовать свой дом. Часто у вас есть определенный цвет, но это не один из цветов, который показывает вам поставщик.
Вчера мой профессор, который является исследователем ГА, упомянул об истинной истории в Германии (извините, у меня нет дальнейших ссылок, да, я могу узнать это, если кто-то просит). Этот парень (позвольте назвать его цветным парнем) привык идти от двери, чтобы помочь людям найти точный цветовой код (в RGB), который был бы закрытым для того, что имел в виду клиент. Вот как он это сделает:
Парень цвета имел обыкновение носить с собой программную программу, которая использовала GA. Раньше он начинал с 4 разных цветов, каждый из которых был закодирован как кодированная хромосома (чье декодированное значение было бы значением RGB). Потребитель выбирает 1 из 4-х цветов (что ближе всего к нему относится). Затем программа назначит максимальную пригодность для этого человека и перейдет к следующему поколению с использованием мутации/кроссовера. Вышеупомянутые шаги будут повторяться до тех пор, пока потребитель не найдет точный цвет, а затем цветной парень, чтобы сказать ему комбинацию RGB!
Назначая максимальную пригодность к цвету, который близок к тому, что потребитель имеет в виду, программа цветного парня увеличивает шансы сходиться к цвету, потребитель точно имеет в виду. Мне было очень весело!
Теперь, когда у меня есть -1, если вы планируете больше -1, PLS. выясните причину этого!
В рамках моей студентской степени CompSci нам была задана проблема поиска оптимальных флагов jvm для виртуальной машины исследования Jikes. Это было оценено с использованием набора тестов Dicappo, который возвращает время на консоль. Я написал распределенный gentic alogirthm, который переключил эти флаги, чтобы улучшить время исполнения набора эталонных тестов, хотя потребовалось несколько дней, чтобы выполнить компенсацию аппаратного дрожания, влияющего на результаты. Единственная проблема заключалась в том, что я не правильно узнал о теории компилятора (которая была целью назначения).
Я мог бы посеять начальную популяцию с существующими флагами по умолчанию, но интересным было то, что алгоритм нашел очень похожую конфигурацию для уровня оптимизации O3 (но на самом деле он был быстрее во многих тестах).
Edit: Также я написал свою собственную структуру генетического алгоритма в Python для назначения и просто использовал команды popen для запуска различных тестов, хотя, если бы это не было назначенное задание, я бы посмотрел на pyEvolve.
Во-первых, "Генетическое программирование" Джонатана Козы (на amazon) - это в значительной степени книга по генетическим и эволюционным методам алгоритма/программирования, со многими примерами. Я настоятельно рекомендую проверить это.
Что касается моего собственного использования генетического алгоритма, я использовал генетический алгоритм (домашний рост) для разработки алгоритма роя для сценария сбора/уничтожения объекта (практическая цель могла бы очистить минное поле). Вот ссылка на документ. Самая интересная часть того, что я делал, - это многоступенчатая функция фитнеса, которая была необходима, поскольку простые функции фитнеса не обеспечивали достаточной информации для генетического алгоритма для достаточной дифференциации между членами населения.
Несколько недель назад я предложил решение на SO с использованием генетических алгоритмов для решения проблемы компоновки графа. Это пример ограниченной проблемы оптимизации.
Кроме того, в области машинного обучения, я реализовал основанную на GA основы классификации правил в c/С++ с нуля.
Я также использовал GA в типовом проекте для обучения искусственных нейронных сетей (ANN) в отличие от использования знаменитого алгоритм backpropagation.
Кроме того, и в рамках моего исследования выпускников я использовал GA в обучении "Скрытые марковские модели" в качестве дополнительного подхода к EM-based алгоритм Baum-Welch (снова в c/С++).
Я являюсь частью команды, изучающей использование Evolutionary Computation (EC) для автоматического исправления ошибок в существующих программах. Мы успешно отремонтировали ряд реальных ошибок в реальных проектах программного обеспечения (см. эта страница проекта).
У нас есть два применения этой методики ремонта ЕС.
Первая (информация о коде и воспроизведении, доступная на странице проекта) развивает абстрактные деревья синтаксиса, анализируемые из существующих программ на C, и реализуется в Ocaml с использованием нашего собственного механизма EC.
Вторая (информация о коде и воспроизведении, доступная на странице проекта), мой личный вклад в проект, развивает сборку x86 или байт-код Java, составленный из программ, написанных на нескольких языках программирования. Это приложение реализовано в Clojure, а также использует собственный пользовательский механизм EC.
Одним из приятных аспектов Evolutionary Computation является простота метода, позволяющая без особых трудностей писать собственные пользовательские реализации. Для хорошего свободно доступного вводного текста по генетическому программированию см. Руководство по использованию генетического программирования .
Сотрудник и я работаем над решением для загрузки грузов на грузовики с использованием различных критериев, которые требует наша компания. Я работаю над решением генетического алгоритма, когда он использует ветвь и привязку с агрессивной обрезкой. Мы все еще находимся в процессе реализации этого решения, но до сих пор мы получали хорошие результаты.
Несколько лет назад я использовал ga для оптимизации грамматик ASR (автоматического распознавания речи) для повышения скорости распознавания. Я начал с довольно простых списков выбора (где ga тестировал комбинации возможных терминов для каждого слота) и проработал мой путь до более открытых и сложных грамматик. Фитнес определяли путем измерения разделения между терминами/последовательностями под видом фонетической дистанционной функции. Я также экспериментировал с созданием слабо эквивалентных вариаций в грамматике, чтобы найти тот, который скомпилирован в более компактное представление (в конце концов я пошел с прямым алгоритмом и резко увеличил размер "языка", который мы могли бы использовать в приложениях).
Совсем недавно я использовал их как гипотезу по умолчанию, против которой проверялось качество решений, генерируемых из разных алгоритмов. Это во многом связано с категоризацией и различными проблемами подбора (т.е. Создает "правило", которое объясняет набор вариантов, сделанных рецензентами по набору данных).
Я создал полную структуру GA под названием "GALAB", чтобы решить многие проблемы:
Я однажды использовал GA для оптимизации хэш-функции для адресов памяти. Адресами были размеры страниц 4K или 8K, поэтому они показали некоторую предсказуемость в битовой схеме адреса (младшие значащие биты все ноль, средние биты постепенно увеличиваются и т.д.). Исходная хеш-функция была "короткой" - она имела тенденцию к кластерным ударам на каждом третьем хэш-ведре. Улучшенный алгоритм имел почти идеальное распределение.
Я не знаю, считается ли домашнее задание...
Во время моих исследований мы выполнили свою собственную программу, чтобы решить проблему Traveling Salesman.
Идея состояла в том, чтобы провести сравнение по нескольким критериям (сложность для сопоставления проблемы, производительности и т.д.), и мы также использовали другие методы, такие как Имитированный отжиг.
Это сработало очень хорошо, но нам потребовалось некоторое время, чтобы понять, как правильно выполнить "воспроизведение": моделирование проблемы под рукой во что-то подходящее для генетического программирования действительно показалось мне самой трудной частью...
Это был интересный курс, так как мы также занимались нейронными сетями и т.п.
Я хотел бы знать, использовал ли кто-либо этот вид программирования в коде "production".
Я построил простую GA для извлечения полезных паттернов из частотного спектра музыки по мере ее воспроизведения. Выход был использован для управления графическими эффектами в плагине winamp.
У меня было несколько GA, настроенных на разные части спектра, а также на различные пределы BPM, поэтому они не склонны сходиться к одной и той же схеме. Выходы из верхней части 4 из каждой совокупности были отправлены в механизм рендеринга.
Интересным побочным эффектом было то, что средняя пригодность для населения была хорошим показателем изменений в музыке, хотя обычно это занимало 4-5 секунд, чтобы понять это.
В рамках моей диссертации я написал общую структуру java для многоцелевого алгоритма оптимизации mPOEMS (оптимизация многопользовательского прототипа с развитыми шагами усовершенствования), который представляет собой GA с использованием эволюционных концепций. Он является общим в том смысле, что все независимые от проблемы части были отделены от проблемных частей, а интерфейс призван использовать структуру только с добавлением проблемно-зависимых частей. Таким образом, тот, кто хочет использовать алгоритм, не должен начинать с нуля, и это облегчает работу.
Здесь вы можете найти код .
Решения, которые вы можете найти с помощью этого алгоритма, были сопоставлены в научной работе с самыми современными алгоритмами SPEA-2 и NSGA, и было доказано, что алгоритм работает сопоставимо или даже лучше, в зависимости от показателей, которые вы принимаете для измерения производительности, и особенно в зависимости от проблемы оптимизации, которую вы ищете.
Здесь вы можете найти .
Также в рамках моей диссертации и доказательства работы я применил эту структуру к проблеме выбора проекта, которая была обнаружена в управлении портфелем. Речь идет о выборе проектов, которые приносят наибольшую ценность компании, поддерживают большую часть стратегии компании или поддерживают любую другую произвольную цель. Например. выбор определенного количества проектов из определенной категории или максимизация синергии проекта,...
Мой тезис, который применяет эту структуру к проблеме выбора проекта: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf
После этого я работал в отделе управления портфелем в одном из 500 дел, где они использовали коммерческое программное обеспечение, которое также применило GA к проблеме выбора проекта/оптимизации портфеля.
Дополнительные ресурсы:
Документация структуры: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf
mPOEMS презентационный документ: http://portal.acm.org/citation.cfm?id=1792634.1792653
На самом деле с небольшим энтузиазмом каждый мог легко адаптировать код общей структуры к произвольной многоцелевой оптимизации.
На работе у меня была следующая проблема: с учетом M задач и N DSP, что было лучшим способом назначить задачи для DSP? "Лучшее" было определено как "минимизация нагрузки самого загруженного DSP". Были разные типы задач, и различные типы задач имели различные характеристики производительности в зависимости от того, где они были назначены, поэтому я закодировал набор заданий на выполнение DSP как "цепочку ДНК", а затем использовал генетический алгоритм для "разведения", лучшая строка назначения, которую я мог бы.
Он работал достаточно хорошо (намного лучше, чем мой предыдущий метод, который должен был оценивать каждую возможную комбинацию... по нетривиальным размерам задачи, потребовалось бы много лет!), единственная проблема заключалась в том, что не было способ определить, было ли достигнуто оптимальное решение или нет. Вы могли бы решить только, было ли текущее "лучшее усилие" достаточно хорошим, или пусть оно работает дольше, чтобы увидеть, может ли оно сделать лучше.
Был проведен конкурс на codechef.com(отличный сайт, кстати, ежемесячные соревнования по программированию), где нужно было решить неразрешимую судоку (нужно приблизиться как можно ближе к нескольким неправильным столбцам/строкам/и т.д.).
Что бы я сделал, было сначала создать идеальную судоку, а затем переопределить поля, которые были предоставлены. Из этой довольно хорошей основы я использовал генетическое программирование для улучшения своего решения.
В этом случае я не мог придумать детерминированный подход, потому что судоку составлял 300 × 300, и поиск занял слишком много времени.
/p >
Я использовал простой генетический алгоритм для оптимизации отношения сигнал/шум волны, которая была представлена как двоичная строка. Перевернув бит несколькими способами в течение нескольких миллионов поколений, я смог произвести преобразование, которое привело к более высокому отношению сигнал-шум этой волны. Алгоритм мог бы также быть "Имитированный отжиг", но в этом случае он не использовался. По своей сути генетические алгоритмы просты, и это было примерно так же просто, как я видел, поэтому я не использовал фреймворк для создания и выбора генерации - только случайное семя и отношение сигнал/шум функции под рукой.
На семинаре в школе мы разрабатываем приложение для создания музыки в музыкальном режиме. Программа была построена на Java, а выход был MIDI файлом с песней. Мы используем различные аппроксимации GA для генерации музыки. Я думаю, что эта программа может быть полезна для изучения новых композиций.
в undergrad мы использовали NERO (комбинацию нейронной сети и генетический алгоритм), чтобы научить игровых роботов принимать интеллектуальные решения. Это было довольно круто.
Я разработал многопоточное колебательное моделирование роботизированной навигации по набору рандомизированной сетки источников пищи и шахт и разработал основанную на генетическом алгоритме стратегию исследования оптимизации роботизированного поведения и выживания наиболее подходящих генов для роботизированной хромосомы. Это было сделано с использованием картографирования и сопоставления каждого цикла итерации.
С тех пор я разработал еще больше игрового поведения. Примером приложения, которое я недавно построил для себя, был генетический алгоритм решения проблемы путешествующих продавцов при поиске маршрута в Великобритании с учетом состояний старта и цели, а также одного/нескольких точек подключения, задержек, аннулирования, строительных работ, часов пик, публичные забастовки, рассмотрение между самыми быстрыми и дешевыми маршрутами. Затем вы получите сбалансированную рекомендацию о том, чтобы маршрут проходил в определенный день.
Как правило, моя стратегия заключается в использовании представления на основе POJO генов, тогда я применяю конкретные реализации интерфейса для выбора, мутации, стратегий кроссовера и точки критериев. Моя фитнес-функция тогда в основном становится довольно сложной, основанной на стратегии и критериях, которые мне нужно применять в качестве эвристической меры.
Я также изучил применение генетического алгоритма в автоматическом тестировании в коде с использованием циклов систематической мутации, когда алгоритм понимает логику и пытается выяснить отчет об ошибке с рекомендациями по исправлениям кода. В принципе, способ оптимизации моего кода и рекомендации по улучшению, а также способ автоматизации обнаружения нового программного кода. Я также пытался использовать генетические алгоритмы для производства музыки среди других приложений.
Как правило, я нахожу эволюционные стратегии, такие как большинство метаэвристических/глобальных стратегий оптимизации, они начинают медленно учиться, но начинают забираться, когда решения становятся все ближе и ближе к состоянию цели и до тех пор, пока ваша фитнес-функция и эвристика хорошо чтобы обеспечить конвергенцию в вашем пространстве поиска.
Однажды я попытался сделать компьютерного игрока для игры Go, исключительно на основе генетического программирования. Каждая программа будет рассматриваться как функция оценки для последовательности ходов. Выпущенные программы были не очень хорошими, хотя даже на довольно уменьшенной плате 3x4.
Я использовал Perl и сам все кодировал. Сегодня я буду делать по-другому.
После прочтения The Blind Watchmaker меня заинтересовала программа pascal. Докинз сказал, что он разработал для создания моделей организмов, которые могли бы развиваться время. Я был достаточно заинтересован, чтобы написать свой собственный, используя Swarm. Я не делал всю эту причудливую графическую графику, но мои "хромосомы" контролировали признаки, которые влияли на способность организмов выжить. Они жили в простом мире и могли сливать его друг против друга и окружающую среду.
Организмы жили или умерли частично из-за случайности, но также основывались на том, насколько эффективно они адаптировались к их местным условиям, насколько хорошо они потребляли питательные вещества и насколько успешно они воспроизводились. Это было весело, но и еще больше доказательств моей жене, что я выродка.
Это было давно, но я закатил GA, чтобы развить то, что было в действительности, для обработки изображений, чтобы удалить следы космических лучей с изображений космического телескопа Хаббла (HST). Стандартный подход заключается в том, чтобы принимать несколько воздействий с помощью Хаббла и сохранять только то, что одинаково во всех изображениях. Поскольку время HST настолько ценно, что я астрономия, и недавно присутствовал на Конгрессе по эволюционным вычислениям, я подумал об использовании GA для очистки отдельных экспозиций.
Люди находились в форме деревьев, которые вносили площадь в 3 × 3 пикселя в качестве входных данных, выполняли некоторые вычисления и выносили решение о том, как и как изменить центральный пиксель. Фитнес оценивали путем сравнения результата с очищенным образцом традиционным способом (например, укладкой стоп).
Это действительно сработало, но недостаточно хорошо, чтобы оправдать первоначальный подход. Если бы мой тезис не был ограничен временем, я мог бы расширить генетический фрагмент, доступный для алгоритма. Я уверен, что я мог бы значительно улучшить его.
Используемые библиотеки: если я правильно помню, IRAF и cfitsio для обработки данных астрономических изображений и ввода-вывода.
Я экспериментировал с GA в юности. Я написал симулятор в Python, который работал следующим образом.
Гены кодировали веса нейронной сети.
Входы нейронной сети были "антеннами", которые обнаруживали касания. Более высокие значения означали очень близко, а 0 означало не касаться.
Выходы были на два "колеса". Если оба колеса пошли вперед, парень пошел вперед. Если колеса были в противоположных направлениях, парень повернулся. Прочность выхода определяла скорость поворота колеса.
Произошел простой лабиринт. Это было действительно просто - глупо. Началось в нижней части экрана и в верхней части, с четырьмя стенами между ними. Каждая стена имела пространство, выведенное случайным образом, поэтому всегда был путь.
Я начал случайных парней (я думал о них как об ошибках) с самого начала. Как только один парень достиг цели, или был достигнут срок, фитнес был рассчитан. Он был обратно пропорционален расстоянию до цели в то время.
Затем я соединил их и "развел" их, чтобы создать следующее поколение. Вероятность быть избранной для разведения была пропорциональна ее пригодности. Иногда это означало, что его размножали с собой многократно, если он имел очень высокую относительную пригодность.
Я думал, что они разработают поведение "левая стена", но они всегда, казалось, следовали чему-то менее оптимальному. В каждом эксперименте ошибки сходились к спиральному шаблону. Они будут прятаться наружу, пока они не коснутся стены справа. Они последуют за этим, а затем, когда они доберутся до разрыва, они соскользнут вниз (вдали от разрыва) и вокруг. Они сделают поворот на 270 градусов влево, а затем обычно попадают в промежуток. Это обеспечило бы их через большинство стен, и часто к цели.
Одна из особенностей, которую я добавил, заключалась в том, чтобы вставить цветовой вектор в гены, чтобы отслеживать взаимосвязь между людьми. После нескольких поколений все они были бы одного цвета, которые говорят мне, что у меня должна быть лучшая стратегия разведения.
Я попытался заставить их разработать лучшую стратегию. Я усложнил нейронную сеть - добавив память и все остальное. Это не помогло. Я всегда видел ту же стратегию.
Я пробовал разные вещи, такие как отдельные генофонды, которые рекомбинировали только после 100 поколений. Но ничто не подтолкнуло бы их к лучшей стратегии. Возможно, это было невозможно.
Еще одна интересная вещь - графическое отображение пригодности с течением времени. Были определенные шаблоны, такие как максимальная пригодность вниз, прежде чем она поднялась. Я никогда не видел рассказ об эволюционной книге об этой возможности.