Джон Холланд – отец генетических алгоритмов

 

Джон Генри Холланд  (John Henry Holland)– известный американский ученый, один из пионеров теории сложных нелинейных и адаптивных систем, "отец" генетических алгоритмов, одного из ключевых направлений ИИ [1–4].

Джон Холланд родился 2 февраля 1929 г. в Форт-Уэйне, штат Индиана (США). В юности он страстно стремился к знаниям, особенно в области "точных" наук. Позже именно математика и физика станут его сильной стороной. В выпускном классе школы, сдавая общегосударственный экзамен по этим предметам, он "недотянул" 2 балла до 1-го места. В итоге он оказался на 3-м месте (в масштабах страны), что позволило ему получить государственную стипендию для поступления в Массачусетский технологический институт (МТИ). В МТИ он имел возможность посещать занятия таких корифеев, как Норберт Винер и Джон Маккарти, что, безусловно, оказало большое влияние на формирование его взглядов.

После окончания в 1950 г. МТИ и получения диплома бакалавра (B.S.) в области физики, Холланд получил приглашение от компании IBM поработать в составе группы инженеров-программистов, перед которой была задача протестировать первый компьютер компании IBM -701.  В качестве тестовой задачи они предложили рассматривать компьютер как некое подобие "смоделированной лабораторной крысы", которая должна искать выход из лабиринта, используя для этого специально построенную упрощенную модель её нервной системы. Как вспоминал впоследствии Холланд, "уже тогда мы поняли, какие преимущества обеспечивает подобное моделирование поведения животных. А преимущество заключается в том, что мы смотрим на ситуацию изнутри, наблюдая за отдельными нейронами, и можем повторить процесс с тех же начальных условий, изменив при этом процедуру обучения" [1].

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

Поработав в IBM, Холланд поступил в Мичиганский университет в г. Энн Арбор (штат Мичиган), где в 1954 г. получил степень магистра искусств (М. А.) в области математики, а в 1959 г. защитил первую в США докторскую диссертацию (Ph. D.) в области информатики (Computer Science). После защиты диссертации он остался в Мичиганском университете, где провел большую работу по становлению нового факультета информатики и разработке основ этой зарождающейся научной дисциплины. Холланд сыграл ключевую роль в создании Мичиганского Центра изучения сложных систем. До настоящего времени он является профессором психологии (с 1988 г.) и профессором электротехники и информатики этого университета.

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

Большое впечатление на него в эти годы произвела прочитанная им книга Рональда А. Фишера «Генетическая теория естественного отбора» (" The Genetic Theory of Natural Selection ", 1930). В этой книге эволюция рассматривалась в качестве механизма адаптации. "Эволюция выступала в качестве способа обучения организма с целью его адаптации (приспособления) к неопределенности окружающей среды. Результаты этого проявлялись лишь через несколько поколений, а не в пределах одной жизни". Он подумал, что если эта теория так хорошо работает для живых организмов, то почему бы её не применить к компьютерным программам. Так Холланд подошел к идее генетических алгоритмов. 

В 1975 г. он опубликовал свою знаменитую книгу "Адаптация в естественных и искусственных системах" [5], которая является основополагающим трудом в области генетических алгоритмов (ГА). Интересно, что за первые 5 лет после того, как она была опубликована, продавалось всего по 100 – 200 экземпляров этой книги и казалось, что она будет предана забвению. Однако уже в последующие годы (и особенно во второй половине 1980-х гг.) число людей, работающих с ГА, – и соответственно интерес к книге Холланда – значительно возросли, что побудило Холланда обновить и переиздать её в 1991 г. Впоследствии эта книга многократно издавалась дополнительными тиражами, и в настоящее время она является одной из наиболее цитируемых работ в области ИИ (по данным на февраль 2009 г., в мире было зафиксировано более 15000 ссылок на эту книгу  [6]). В своей книге Холланд впервые ввел термин " генетический алгоритм " и дал строгое математическое обоснованиие этого класса методов оптимизации. Суть ГА заключается в построении процедур поиска оптимальных (или приближенно оптимальных) решений задачи на основе механизмов естественного отбора и наследования. В ГА используется эволюционный принцип естественного отбора Чарлза Дарвина – "Выживает наиболее приспособленный" (" Survives the fittest ").

При описании ГА Холланд использовал такие (ставшие сегодня уже привычными для нас) понятия, заимствованные из генетики, как "хромосома", "ген", "популяция", "функция приспособленности", "генетические операции" – "рекомбинация", "отбор", "кроссинговер", "мутация" и др. В книге Холланда была сформулирована и доказана фундаментальная теорема ГА – "теорема о схемах" (schemata theorem), которая дает формализованный подход к построению ГА в виде наборов "кирпичиков" – "строительных блоков" (building blocks). Теорема о схемах (шаблонах), несмотря на существенные ограничения области её применения (с современной точки зрения), является сегодня обязательным компонентом разделов, посвященных ГА, в учебниках по ИИ. Помимо математических основ построения ГА, Холланд рассмотрел в своей книге также общие принципы построения классифицирующих систем (classifier systems) на основе ГА, которые в настоящее время нашли широкое применение в интеллектуальных информационно-управляющих системах. 

Однако историческая заслуга Холланда состоит не только в том, что он явился основоположником теории ГА, но и в том, что он создал свою признанную научную школу в области ГА, которая развила и обогатила его идеи как в теоретическом плане, так и (что не менее существенно) в вопросах практического применения ГА в различных областях науки и техники. Одной из первых таких работ, выполненных под руководством Дж. Холланда, является защищенная в 1975 г. докторская диссертациия его ученика Кеннета Де Йонга (Kenneth A. De Jong) "Анализ поведения одного класса генетических адаптивных систем" [7]. В качестве составной части своей работы Де Йонг предложил 5 различных видов тестовых функций, выбранных им для оценки качества произвольных ГА. Используя эти тестовые функции и предложенные им метрики качества ГА (которые и до сих пор используются многими исследователями в области ГА), Де Йонг впервые провел анализ влияния 4-х базовых параметров ГА (размер популяции, вероятность кроссинговера, вероятность мутации, число поколений) на эффективность работы ГА.

Впоследствии многие из учеников Де Йонга – Стив Смит (Stieve Smith), Джон Грефенштетте (John Grefenstette) и др. внесли свой существенный вклад в развитие теории ГА. Так, Грефенштетте разработал программную реализацию ГА, названную им GENESIS, которая в различных версиях получила широкое распространение в конце 1980-х гг. Он также был ответственным за подготовку и издание трудов 1-й Международной конференции по ГА (1985 г.).

Другой из учеников Холланда, Дэвид Гольдберг (David Goldberg) сконцентрировался на практических приложениях ГА. Проработав длительное время в качестве инженера на насосной газоперекачивающей станции, он защитил в 1983 г. докторскую диссертацию (Ph. D.), посвященную анализу установившихся режимов работы протяженного газопровода с 10 компрессорными станциями и выбору оптимальной стратегии его обслуживания с учетом реальных ограничений по давлению газа. В 1989 г. Гольдберг опубликовал свою книгу "Генетические алгоритмы в задачах поиска, оптимизации и машинного обучения" [8], которая стала одной из наиболее значимых и цитируемых книг по ГА. Появление этой книги, содержащей не только обзор фактического состояния работ в области ГА на момент её издания, но и анализ перспективных направлений исследований, сопровождающийся примерами программной реализации ГА для решения конкретных прикладных задач, способствовало значительному росту интереса у многих (и, в первую очередь, молодых) исследователей к указанной проблематике. 

Отмечая роль Дж. Холланда как "отца" генетических алгоритмов, Лоуренс Дэвис (Lawrence Davis), один из мировых авторитетов в области ГА, позднее писал [3]: "Джон Холланд создал область генетических алгоритмов. Эта область не существовала бы, если бы он не решил использовать ту мощь, которая свойственна генетическим процессам, в начале 1970-х годов и не действовал бы как технический и политический лидер в данной области с момента её зарождения до настоящего времени. Наше понимание уникальных свойств генетических алгоритмов во многом сформировалось благодаря той кропотливой и вдумчивой работе, которую вели Холланд и его ученики с самых первых лет возникновения этого направления и до наших дней".

Заметим, что усилиями Дж. Холланда, его учеников и многочисленных последователей по всему миру, сегодня на базе первоначальных (достаточно простых, "примитивных") ГА созданы не только более совершенные модификации ГА, но и ряд новых, интенсивно развивающихся научных направлений – генетическое программирование, эволюционное программирование, эволюционные стратегии и др., имеющие многообещающие перспективы применения для решения широкого класса задач управления и принятия решений [9–10].

В 1990-х гг. спектр научных интересов Холланда сместился в сторону вопросов, связанных с изучением сложных адаптивных систем различной физической природы на основе многоагентного подхода, теории сложности, механизмов самоорганизации за счет кооперативных процессов (синергетики) и эмерджентности (целостности). Оставаясь профессором Мичиганского университета, он совмещает эту деятельность с работой в качестве приглашенного (external) профессора Института Санта Фе. Это независимая некоммерческая научно-исследовательская организация, созданная в 1984 г. в г. Санта Фе (штат Нью-Мексико, США) с целью проведения междисциплинарных научных исследований в области фундаментальных принципов построения и функционирования сложных систем. Холланд является активным участником проекта Echo, выполняемого под эгидой Института Санта Фе и направленного на разработку инструментальных средств моделирования механизмов обработки информации в сложных адаптивных системах, состоящих из большого числа взаимодействующих адаптивных агентов. Наиболее значимые публикации за этот период – книги "Скрытый порядок: Как адаптация определяет сложность" [11] и "Эмерджментность: От хаоса к порядку" [12], опубликованные Холландом соответственно в 1995 и 1998 гг.

В 2007 году группа из 10 видных американских ученых, в состав которой входил и Джон Холланд, выступила с международной инициативой "Десятилетие разума" (" Decade of the Mind "). В своем обращении, опубликованном в журнале " Science " (сентябрь 2007 г.), они выделили основные направления перспективных исследований, способствующих пониманию, совершенствованию и моделированию человеческого разума. По мнению авторов обращения, "глубокое понимание того, как разум воспринимает мир, думает и действует, сейчас у нас почти на ладони". Обращение заканчивается выражением уверенности, что в течение ближайших 10 лет будут окончательно выяснены основные механизмы мышления, что приведет к улучшению жизни людей и, возможно, даже к появлению объектов, обладающих интеллектом, значительно превосходящим интеллект человека.

Холланд ведет активную общественную деятельность. Он читает лекции в различных странах мира, выступает с пленарными докладами на представительных Международных конференциях, является членом редакционных коллегий многих международных журналов. Он является членом Центра по изучению сложных систем в Мичиганском университете, сопредседателем Ученого совета и членом попечительского совета Института Санта Фе, членом правления Международного общества генетических и эволюционных вычислений, членом Всемирного экономического форума.

Заслуги Холланда отмечены премией Маккартура, медалью Леви Института Бенджамина Франклина и рядом других наград. В 1999 г. Дж. Холланд был удостоен Премии Пендера (Pender Award) – высшая награда Пенсильванского университета (США) за "основополагающие труды по созданию генетических алгоритмов и инновационные исследования в области теории сложности и адаптивных систем".

Завершим этот биографический экскурс пророческими словами Д. Гольдберга, высказанными им в заключении его получившей широкую известность книги [8]: "Представляя себе сегодня современное состояние генетических алгоритмов, их необозримые возможности и задачи, мы всё более укрепляемся в понимании того, как много создала природная генетика, в уверенности в том, что мы уже сделали, и в ещё большем ожидании того, что нам ещё предстоит открыть".

 

 

                 Использованные источники

 

1^*. John Henry Holland – [Электронный ресурс]. – Режим доступа: http://cs.oswego. edu/~blue/hx/courses/cogsci1/s2001.

2^*. John Henry Holland/ Biography – [Электронный ресурс]. – Pежим доступа: http://www.encyclopedia.britannica/biography/John _Henry _Holland.html.

 3*. Eberhart R. C., Shi Yuhui. Computational Intelligence: Concepts to Impelementation, Morgan Kaufman Pub., 2007.

4*. Холланд Джон Генри – [Электронный ресурс]. – Режим доступа: http:// ru.wikipedia.org/w/index.php?title=Холланд_Джон_ Генри&oldid=53955278.

5. Holland J. H. Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, 1975.

6. Reynolds R. G. A Geneology of Computational Intelligence Books// IEEE Computational Intelligence Magazine. – Vol. 4. Nu.1. Feb. 2009.– P. 56–61.

7. De Jong K.A. An analysis of the behaviour of a class of genetic adaptive systems, Ph. D. thesis, Univ. of Michigan, 1975.

8. Coldberg D. E. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Pub. Co., Inc., 1989.

9. Курейчик В. В. Генетические алгоритмы. Состояние. Проблемы. Перспективы // Известия РАН. Теория и системы управления. – № 1. – 1999. – С. 144 –160.

10. Васильев В. И., Ильясов Б. Г. Интеллектуальные системы управления с использованием генетических алгоритмов // Приложение к журналу «Информационные технологии». – № 12. – 2000. – 24 с.

11. Holland J. H. Hidden Order: How Adaption Builds Complexity, Basic Books, 1995.

12. Holland J. H. Emergence: From Chaos to Order, Addison-Wesley Pub. Co. 1998.