CFA LogoCFA Logo Computer
Новости Статьи Магазин Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2002 ГОД

Выживет сильнейший

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

Проблема решения сложных задач

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

В частности, на решение некоторых аналитических задач в области финансов мощным вычислительным комплексам могут понадобиться недели, хотя на финансовом рынке оперативность решения зачастую гораздо важнее его точности. Например, пока компьютер определяет оптимальную комбинацию инвестиций в ценные бумаги, конъюнктура фондового рынка может измениться буквально катастрофически. И, конечно же, найденное решение окажется несвоевременным. Уже в восьмидесятые годы инвестиционные компании начали приглашать на работу ученых с целью разработки эффективных методов решений подобных задач. Самым известным из них, пожалуй, стал Генри Генсон (Henry Hanson), бывший физик из Университета Брауна (Brown University).

Генри Генсон начал свою блистательную карьеру финансового аналитика на Уоллстрит в восьмидесятых годах. Вот что сказал глава инвестиционного фонда First Boston’s Senft во время одного из интервью в отношении Генсона и других «физиков», работающих на Уоллстрит: «Они используют компьютеры, чтобы получить более-менее правильные решения за короткий промежуток времени — около пятнадцати минут. Это позволяет избежать значительного изменения цен на фондовом рынке за время решения задачи. Конечно, нам мало понятно, как они это делают, но можно с уверенностью сказать, что их методы — это совершенно иная идеология инвестиционного менеджмента».

Новая идеология решения сложных задач

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

Интересно заметить, что главным идеологом нового подхода к решению задач оптимизации стал отнюдь не Генри Генсон. Им стал, сам того не подозревая, Чарльз Дарвин. Как понимаете, многое из того, что происходит в нашем мире, можно объяснить теорией эволюции, наследственности, естественного отбора. Не исключение — эффективные методы решения сложных задач анализа и оптимизации.

Именно фундаментальная работа Чарльза Дарвина «Происхождение Видов», опубликованная в 1859 году, вдохновила в середине 60-х годов XX столетия другого выдающегося ученого, Джона Голланда (John Holland), профессора психологии и компьютерных наук из Университета Мичиган, на создание теории генетических алгоритмов.

Генетические алгоритмы

Определение

Генетические алгоритмы могут быть определены как методы поиска оптимального решения сложных задач с многочисленными параметрами, в основе которых лежит эволюция промежуточных решений. Первоначальные варианты решения задачи генерируются произвольно. Затем наиболее подходящие первоначальные решения «скрещиваются» между собой для получения «потомков», то есть еще более подходящих решений. Процесс повторяется до тех пор, пока не будет найдено оптимальное (или близкое к оптимальному) решение. Процесс также может быть прерван из-за временных ограничений. Как видите, этот процесс аналогичен процессу естественного отбора в природе, который был описан Чарльзом Дарвином.

Пример реализации генетического алгоритма

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

Кодирование вариантов решения задачи

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

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

Скрещивание

Следующим шагом в работе алгоритма является так называемое скрещивание. В процессе скрещивания Решение 1 и Решение 2 «обмениваются» друг с другом значениями разрядов. Для реализации обмена произвольным образом выбирается точка пересечения, затем Решение 1 и Решение 2 «обмениваются» бинарными последовательностями, Рис. 2производя на свет «потомков», то есть новые варианты решения задачи (рис. 2)

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

Мутация

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

Приспособленность потомков

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

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

Применение генетических алгоритмов

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

Например, инженеры General Electrics уже давно используют генетические алгоритмы для создания реактивных двигателей. Подобное применение генетических алгоритмов объясняется тем, что для решения таких задач требуется учитывать свыше ста параметров и около 50 сложнейших уравнений. Известный Американский производитель пива Coors использует генетические алгоритмы для оптимизации процесса отправки продукции заказчикам. Военно-морские силы США используют генетические алгоритмы для повышения эффективности обслуживания самолетов авианосцами.

Новое направление в разработке программного обеспечения

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

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © sector.biz.ua 2006-2015 design by Vadim Popov