|
Номер 3 |
|
Генетические алгоритмы. Часть вторая. Реализация алгоритмов борьбы за существование Исключительным свойством живых организмов является способность меняться. Мы можем терять приспособленность или наоборот - повышать свой уровень. Одно очевидно, что у более сильной особи (в плане как физическом так и социальном) шансов попасть в следующее поколение гораздо больше. Именно на этом принципе реализуем следующий этап - "выживание сильнейших". Наша задача состоит в определении условного уровня хромосом - жизненного показателя (фитнес-функции). В условиях, рассматриваемой в первой части рассылки (все рассылки есть в архиве сайта) задачи - определении наименьшего пути достаточно легко определить лучшую хромосому. Используем простейший алгоритм вычисления расстояния между двумя точками. Алгоритм применим в виде функции. На входе - хромосома-маршрут, а на выходе - относительное значение длины пути. Подобная фитнес-функция позволит легко сравнивать хромосомы и выбирать более приспособленную - выживают сильнейшие!
Однако фитнес-функция не создает новых хромосом. Для этого конечно можно включить генератор хромосом еще раз, однако в условиях задачи комиояджера с 256 пунктами это становится невозможным. Для определения уникального пункта потребуется 8 бит - 28 = 256 - 1 байт, а для назначения пути - цепочка из 256 байт. Вероятность появления оптимального маршрута ничтожно мала.
Существует множество решений данной проблемы, здесь я предложу наиболее простое, но в тоже время достаточно эффективное. Представим, что мы выбираем две приспособленные хромосомы, сравниваем все биты. Совпавшие биты (0 и 0 или 1 и 1) оставляем без изменения, а не совпавшие определяем через генератор случайных чисел. Также предусмотрим возможность изменения и совпавших генов (бит), однако вероятность мутации уменьшим до порядка 1 мутация на сто процессов отбора. В результате в каждым поколением качество хромосом будет возрастать.
Конечно мы несколько подталкиваем процесс мутации в нужном направлении, что противоречит естественной параллели, однако подобные действия оправданы необходимостью выполнения задачи в разумный срок. В скором времени на сайте будут выложены исходные коды для обеспечения алгоритмов мутации хромосом
Теория на практике Конечно нам довольно часто приходится решать задачу нахождения оптимального пути, но естественно хотелось бы узнать о возможность применения генетических алгоритмов и в других областях человеческой деятельности. Наиболее популярным стало использование генетических алгоритмов для составления оптимального расписания/оптимального распорядка для.
Входные данные имею достаточно простой вид - длительность занятия и его примерное время проведения. А фитнес-функция определяет насколько новое расписание экономит время всех задействованных людей.
Аналогичные задачи решаются при нахождении оптимального автобусного маршрута (совокупность времени и траектории) но наиболее интересным, на мой взгляд, применением генетических алгоритмов является их использование в нейросетях или системах искусственной жизни, но об этом потом.
В заключении тематики генетических алгоритмов Надеюсь, что два последних номера были для вас познавательны и интересны, если кто-то заинтересовался и пробовал написать какие-то программы - присылайте. Скоро на сайте появятся ссылки по генетическим алгоритмам (в разделе "Ссылки" уже есть парочка) - я сообщу об этом дополнительно в рассылке.
В заключении к генетическим алгоритмам хочу сказать, что реально никто не применяет все технологии в совокупности, возможно, что именно ваше решение, станет серьезным шагом на пути к новым достижениям.
|
|
Новости |
|
В минувший понедельник (25 июня 2000) крупнейшие агентства новостей сообщали о крупнейшем достижении ученых - почти полностью расшифрован геном человека... На сайте появилась новая статья на эту тему |
|
В следующем номере |
|
Искусственный интеллект. Основные понятия. |
|
Новости сайта - http://aifuture.chat.ru |
|
Новый материал Геном человека. Какие перспективы для AI? Рассылка Периодичность рассылки: раз в неделю, подписывайтесь на сайте Планируется после выпуска этого номера перевести рассылку в основной каталог - подписчиков будет побольше (все старые номера рассылки есть на сайте) Почта Если вы хотите увидеть в рассылке какую- либо тему - пишите, присылайте материал (см рубрику "Контакты") Как вам новое оформление? Лучше получать подписку в виде html - размер чуть больше, а читать приятнее, формулы отображаются нормально Реклама - по вопросам рекламы в рассылках обращаться по указанным адресам, в поле Subject указать реклама. Важно - если кто-то писал на ai_future@pisem.net и не получил ответа, приношу свои извинения - были проблемы с ящиком. Для писем открыт резервный адрес - s_copy@mail.ru |
|
Алексей Савкин Искусственный интеллект - взгляд в будущее mailto: ai_future@pisem.net или s_copy@mail.ru (в поле Subject укажите: "Рассылка") |