Каковы хорошие примеры генетических алгоритмов / решений для генетического программирования? [закрыто]

Генетические алгоритмы (GA) и генетическое программирование (GP) являются интересными областями исследований.

Я хотел бы знать о конкретных проблемах, которые вы решили с помощью GA / GP, и о том, какие библиотеки / фреймворки вы использовали, если не использовали свои собственные.

Вопросы:

• Какие проблемы вы использовали GA / GP для решения?
• Какие библиотеки / фреймворки вы использовали?

Я ищу опыт из первых рук, поэтому, пожалуйста, не отвечайте, если у вас нет этого.

Не домашнее задание.

Моя первая работа в качестве профессионального программиста (1995) - написание системы автоматической торговли на основе генетических алгоритмов для фьючерсов S & P500. Приложение было написано на Visual Basic 3 [!], И я понятия не имею, как я тогда что-то делал, поскольку в VB3 даже не было классов.

Приложение началось с популяции случайно сгенерированных строк фиксированной длины (часть «гена»), каждая из которых соответствовала определенной форме в поминутных ценовых данных фьючерсов S & P500, а также конкретному заказу. (покупка или продажа) и суммы стоп-лосса и стоп-прибыли. У каждой строки (или «гена») были показатели прибыльности, оцененные с помощью анализа исторических данных за 3 года; всякий раз, когда указанная «форма» соответствовала историческим данным, я принимал соответствующий ордер на покупку или продажу и оценивал результат сделки. Я добавил предостережение о том, что каждый ген начинается с фиксированной суммы денег и, таким образом, потенциально может разориться и быть полностью удаленным из генофонда.

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

К сожалению, у меня никогда не было возможности использовать эту систему вживую, поскольку мой начальник потерял около 100 000 долларов менее чем за 3 месяца, торгуя традиционным способом, и он потерял желание продолжать проект. Оглядываясь назад, я думаю, что система принесла бы огромную прибыль - не потому, что я обязательно что-то делал правильно, а потому, что популяция генов, которые я произвела, оказалась склонной к заказам на покупку (в отличие от заказов на продажу) примерно в 5 раз: 1 соотношение. И, как мы знаем из нашего прошлого 20/20, рынок немного вырос после 1995 года.

Я сделал маленьких тварей, которые жили в этом маленьком мире. У них был мозг нейронной сети, который получил некоторый вклад от мира, и результат был вектором для движения среди других действий. Их мозги были "генами".

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

Окружающая среда содержала пищу и опасности. Пища увеличивает энергию, и когда у вас достаточно энергии, вы можете спариваться. Опасности уменьшат энергию, и если энергия будет равна 0, они умрут.

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

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

Тогда я попробовал что-то интересное. Я мертвые существа стали бы едой. Попробуйте угадать, что случилось! Два типа существ эволюционировали: те, которые нападали, как в роях, и те, у которых было большое избегание.

Так какой урок здесь? Общение означает сотрудничество. Как только вы вводите элемент, где причинение вреда другому означает, что вы что-то получаете, сотрудничество разрушается.

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

Редактировать:

Я написал это на C ++ без использования фреймворков. Написал свою собственную нейронную сеть и код GA. Эрик, спасибо, что сказал, что это правдоподобно. Люди обычно не верят в силу ГА (хотя ограничения очевидны), пока они не поигрались с ней. GA прост, но не упрощен.

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

Вот демонстрационный код для примера выживания: http://www.mempko.com/darcs/neural/demos/eaters/ Инструкции по сборке:

• Установите darcs, libboost, liballegro, gcc, cmake, make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

В январе 2004 года со мной связалась Philips New Display Technologies, которая создавала электронику для первого в истории коммерческого электронного чернил - Sony Librie, которая была выпущена только в Японии, за годы до того, как Amazon Kindle и другие компании вышли на рынок в США. Европа.

У инженеров Philips была большая проблема. За несколько месяцев до того, как продукт должен был появиться на рынке, они все еще появлялись на экране при смене страниц. Проблема была в 200 драйверах, которые создавали электростатическое поле. У каждого из этих драйверов было определенное напряжение, которое должно было быть установлено между 0 и 1000 мВ или что-то вроде этого. Но если бы вы изменили один из них, это изменило бы все.

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

Главный инженер связался со мной, потому что я ранее выпустил библиотеку генетического программирования для сообщества открытого кода. Он спросил, помогут ли GP / GA и смогу ли я принять участие. Я сделал это, и около месяца мы работали вместе, я писал и настраивал библиотеку GA на синтетических данных, а он интегрировал ее в свою систему. Затем, в один из выходных, они позволили ему начать жить с реальной вещью.

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

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

Я использовал GA, чтобы оптимизировать распределение мест на моей свадьбе. 80 гостей за 10 столами. Функция оценки была основана на том, чтобы держать людей с их датами, объединять людей с чем-то общим и держать людей с противоположными взглядами за отдельными столами.

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

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

Обновление : потому что пара человек спросили, как ...

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

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

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

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

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

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

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

Я сделал все это с помощью Perl. Один запуск программного обеспечения на довольно старой машине linux займет 1-2 часа (20 минут для загрузки данных по каналу WAN, остальное время затрачивается на работу). Размер любого данного поколения был ограничен доступной оперативной памятью. Я запускал его снова и снова с небольшими изменениями параметров в поисках особенно хорошего набора результатов.

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

Футбол Чаевые. Я построил систему GA, чтобы предсказать результаты игр в AFL (Aussie Rules Football).

Несколько лет назад мне наскучил стандартный рабочий футбольный пул, все просто выходили в интернет и выбирали результаты от какого-то ученого мужа в прессе. Итак, я подумал, что не может быть слишком сложно победить кучу специалистов по журналистике, не так ли? Моей первой мыслью было взять результаты рейтингов Massey, а затем раскрыть в конце сезона мою стратегию после завоевания славы и славы. Однако по причинам, которые я никогда не обнаруживал, Мэсси не отслеживает AFL. Циник во мне верит, что это потому, что исход каждой игры AFL в основном стал случайным, но мои жалобы на недавние изменения правил относятся к другому форуму.

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

На практике система находила бы решения, которые точно предсказывали более 90% результатов прошлых игр. Затем он успешно выберет около 60-80% игр для предстоящей недели (то есть недели, не входящей в тренировочный набор).

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

Я построил все с нуля, без фреймворка.

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

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

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

Я разработал систему GA домашнего приготовления для системы лазерных 3D-профилей поверхности, которую моя компания разработала для грузовой промышленности еще в 1992 году. Система основывалась на трехмерной триангуляции и использовала нестандартный лазерный линейный сканер, камеру 512x512 (с настраиваемым захватом hw). Расстояние между камерой и лазером никогда не было точным, и фокус камеры не должен был быть найден в 256 256 местах, как вы ожидали!

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

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

Уловка сработала. Я был ошеломлен по меньшей мере! В течение примерно 10 поколений мой «виртуальный» куб (генерируемый из необработанного сканирования и воссозданный по параметрам калибровки) фактически выглядел как куб! Примерно через 50 поколений у меня была необходимая калибровка.

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

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

Цвет парень использовал носить с собой программное обеспечение , которое используется GA. Он имел обыкновение начинать с 4 разных цветов, каждый из которых закодирован как закодированная хромосома (чье декодированное значение будет значением RGB). Потребитель выбирает 1 из 4 цветов (который наиболее близок к тому, что он / она имеет в виду). Затем программа присвоит этому человеку максимальную приспособленность и перейдет к следующему поколению, используя мутацию / кроссовер . Вышеприведенные шаги будут повторяться до тех пор, пока потребитель не найдет точный цвет, а затем парень по цвету скажет ему комбинацию RGB!

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

Теперь, когда у меня есть -1, если вы планируете больше -1, пожалуйста. выяснить причину этого!

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

Также в области машинного обучения я с нуля реализовал систему правил классификации на основе GA в c / c ++.
Я также использовал GA в примере проекта для обучения искусственных нейронных сетей (ANN), в отличие от использования известного алгоритма обратного распространения .

Кроме того, и как часть моих исследований в аспирантуре, я использовал GA в обучении скрытых марковских моделей в качестве дополнительного подхода к алгоритму Баума-Уэлча на основе ЭМ (снова в c / c ++).

В рамках моей степени бакалавра CompSci нам была поставлена ​​задача найти оптимальные флаги jvm для исследовательской виртуальной машины Jikes. Это было оценено с помощью набора тестов Dicappo, который возвращает время на консоль. Я написал распределенный джентльменский логарифм, в котором эти флаги были изменены, чтобы улучшить время выполнения набора тестов, хотя потребовались дни, чтобы компенсировать аппаратное дрожание, влияющее на результаты. Единственная проблема заключалась в том, что я не изучал теорию компилятора (что и было целью задания).

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

Редактировать: Также я написал свою собственную структуру генетического алгоритма в Python для назначения и просто использовал команды popen для запуска различных тестов, хотя, если бы это не было оцененное задание, я бы посмотрел на pyEvolve.

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

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

Я являюсь частью команды, исследующей использование Evolutionary Computation (EC) для автоматического исправления ошибок в существующих программах. Мы успешно исправили ряд реальных ошибок в реальных программных проектах (см. Домашнюю страницу этого проекта ).

У нас есть два применения этой техники ремонта EC.

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

• Второй ( код и информация о воспроизведении, доступные на странице проекта ), мой личный вклад в проект, развивает сборку x86 или байт-код Java, скомпилированный из программ, написанных на нескольких языках программирования. Это приложение реализовано в Clojure, а также использует собственный встроенный EC-движок.

Одним из приятных аспектов Evolutionary Computation является простота техники, позволяющая без особых трудностей писать свои собственные реализации. Хороший свободно доступный вводный текст по генетическому программированию см. В Полевом руководстве по генетическому программированию .

Мы с коллегой работаем над решением для погрузки грузов на грузовики, используя различные критерии, которые требует наша компания. Я работал над решением Genetic Algorithm, пока он использует Branch And Bound с агрессивным сокращением. Мы все еще находимся в процессе внедрения этого решения, но до сих пор добиваемся хороших результатов.

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

Совсем недавно я использовал их в качестве гипотезы по умолчанию для проверки качества решений, генерируемых различными алгоритмами. Это в значительной степени связано с категоризацией и различными типами проблем подбора (т. Е. Создать «правило», которое объясняет набор вариантов, сделанных рецензентами над наборами данных).

Я сделал полную структуру GA под названием "GALAB", чтобы решить множество проблем:

• определение местоположения GSM ANT (BTS) для уменьшения перекрытия и отсутствия мест.
• Планирование проекта с ограничением ресурсов.
• Эволюционная картина создания. ( Evopic )
• Задача коммивояжера.
• N-Queen и N-Color проблемы.
• Рыцарский тур и рюкзак.
• Загадки Магический квадрат и Судоку.
• сжатие строк, основанное на проблеме суперструн.
• 2D Упаковка.
• Крошечный искусственный жизни приложение.
• Пазл рубик.

Однажды я использовал GA для оптимизации хеш-функции для адресов памяти. Адреса имели размеры страниц 4K или 8K, поэтому они демонстрировали некоторую предсказуемость в битовой структуре адреса (младшие значащие биты - все ноль; средние биты регулярно увеличивались и т. Д.). Первоначальная хеш-функция была «короткой» - она ​​имела тенденцию к попаданию в кластер. на каждом третьем хэш-ведре. У улучшенного алгоритма было почти идеальное распределение.

Я не знаю, считается ли домашнее задание ...

Во время учебы мы разработали собственную программу для решения проблемы коммивояжера.

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

Это сработало довольно хорошо, но нам потребовалось некоторое время, чтобы понять, как правильно выполнить фазу «воспроизведения»: моделирование рассматриваемой проблемы в нечто подходящее для генетического программирования действительно показалось мне самой сложной частью ...

Это был интересный курс, так как мы также баловались с нейронными сетями и тому подобным.

Я хотел бы знать, использовал ли кто-нибудь этот вид программирования в «производственном» коде.

Я построил простой GA для извлечения полезных паттернов из частотного спектра музыки во время ее воспроизведения. Вывод использовался для управления графическими эффектами в плагине winamp.

• Ввод: несколько кадров FFT (представьте 2D-массив с плавающей точкой)
• Выход: значение с плавающей запятой (взвешенная сумма входных данных) с пороговым значением 0,0 или 1,0
• Гены: входные веса
• Фитнес-функция: комбинация коэффициента заполнения, ширины импульса и ударов в минуту в разумных пределах.

У меня было несколько GA, настроенных на разные части спектра, а также на разные пределы BPM, поэтому они не имели тенденцию сходиться к одному и тому же шаблону. Выводы из топ-4 от каждого населения были отправлены в механизм рендеринга.

Интересным побочным эффектом было то, что средняя пригодность по всему населению была хорошим индикатором для изменений в музыке, хотя обычно это занимало 4-5 секунд, чтобы понять это.

В рамках своей диссертации я написал общую Java-инфраструктуру для многоцелевого алгоритма оптимизации mPOEMS (Многообъективная оптимизация прототипа с развитыми шагами улучшения), который представляет собой GA с использованием эволюционных концепций. Он является общим в том смысле, что все проблемно-независимые части были отделены от проблемно-зависимых частей, и интерфейс должен использовать платформу только с добавлением проблемно-зависимых частей. Таким образом, тот, кто хочет использовать алгоритм, не должен начинать с нуля, и это значительно облегчает работу.

Вы можете найти код здесь .

Решения, которые вы можете найти с помощью этого алгоритма, сравнивались в научной работе с современными алгоритмами SPEA-2 и NSGA, и было доказано, что алгоритм работает сопоставимо или даже лучше, в зависимости от показателей, которые вы используете. для измерения производительности, особенно в зависимости от проблемы оптимизации, которую вы рассматриваете.

Вы можете найти это здесь .

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

Мой тезис, который применяет эту структуру к проблеме выбора проекта: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

После этого я работал в отделе управления портфелем в одном из Fortune 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, и поиск занял бы слишком много времени.

Я использовал простой генетический алгоритм для оптимизации отношения сигнал / шум волны, которая была представлена ​​в виде двоичной строки. Перевернув биты определенным образом на протяжении нескольких миллионов поколений, я смог произвести преобразование, которое привело к более высокому отношению сигнал / шум этой волны. Алгоритм также мог быть «Имитацией отжига», но в этом случае он не использовался. По своей сути генетические алгоритмы просты, и это был примерно такой же простой случай использования, который я видел, поэтому я не использовал каркас для создания и отбора поколений - только случайное начальное число и отношение сигнал-шум функция под рукой.

На семинаре в школе мы разрабатываем приложение для генерации музыки в музыкальном режиме. Программа была построена на Java, а на выходе был MIDI-файл с песней. Мы используем отличительные подходы GA для создания музыки. Я думаю, что эта программа может быть полезна для изучения новых композиций.

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

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

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

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

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

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

Однажды я попытался сделать компьютерный плеер для игры в Го, основанный исключительно на генетическом программировании. Каждая программа будет рассматриваться как функция оценки для последовательности ходов. Созданные программы были не очень хорошими, даже на довольно миниатюрной доске 3х4.

Я использовал Perl и сам все кодировал. Я бы сделал все по-другому сегодня.

После прочтения «Слепого часовщика» меня заинтересовала паскальская программа, которую, по словам Докинза, он разработал для создания моделей организмов, способных эволюционировать со временем. Я был достаточно заинтересован, чтобы написать свой собственный, используя Swarm . Я не делал все его причудливые графические изображения, но мои «хромосомы» контролировали черты, которые влияли на способность организма выживать. Они жили в простом мире и могли противостоять друг другу и своему окружению.

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

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

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

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

Используемые библиотеки: если я правильно помню, IRAF и cfitsio для обработки данных астрономических изображений и ввода / вывода.

Я экспериментировал с GA в юности. Я написал симулятор на Python, который работал следующим образом.

Гены закодировали веса нейронной сети.

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

Выходы были на два "колеса". Если оба колеса пошли вперед, парень пошел вперед. Если колеса были в противоположных направлениях, парень повернулся. Сила выхода определяла скорость поворота колеса.

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

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

Затем я соединил их и «разводил», чтобы создать следующее поколение. Вероятность быть выбранным для разведения была пропорциональна его пригодности. Иногда это означало, что человек разводился сам с собой, если у него была очень высокая относительная приспособленность.

Я думал, что у них появится поведение «объятия левой стены», но они всегда, казалось, следовали чему-то менее оптимальному. В каждом эксперименте ошибки сходились по спирали. Они будут двигаться наружу, пока не коснутся стены справа. Они следовали за этим, затем, когда они добрались до разрыва, они пошли вниз (в сторону от разрыва) и вокруг. Они делали поворот на 270 градусов влево, а затем обычно входили в пропасть. Это позволит им пройти через большинство стен и часто к цели.

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

Я пытался заставить их разработать лучшую стратегию. Я усложнил нейронную сеть - добавил память и все. Это не помогло. Я всегда видел одну и ту же стратегию.

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

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