Адаптация по Гауссу (GA) , также называемая нормальной или естественной адаптацией (NA), представляет собой эволюционный алгоритм, разработанный для максимизации выхода продукции из-за статистического отклонения значений компонентов систем обработки сигналов . Короче говоря, GA - это стохастический адаптивный процесс, в котором количество выборок n- мерного вектора x [ x T = ( x 1 , x 2 , ..., x n )] берутся из многомерного распределения Гаусса , N ( м , м), Имеющая средние м и момент матрицы M . Образцы проходят проверку на соответствие или не соответствует требованиям. Моменты первого и второго порядка гауссиана, ограниченного проходными выборками, равны m * и M * .
Результат x как проходной выборки определяется функцией s ( x ), 0 < s ( x ) < q ≤ 1, так что s ( x ) - это вероятность того, что x будет выбран в качестве проходной выборки. Средняя вероятность нахождения проходных выборок (урожайность) равна
Тогда теорема GA гласит:
Для любого s ( x ) и любого значения P < q всегда существует гауссовский pdf [ функция плотности вероятности ], адаптированный для максимальной дисперсии. Необходимые условия для локального оптимума: m = m * и M пропорционально M *. Также решается двойная проблема: максимальное значение P при сохранении постоянной дисперсии (Kjellström, 1991).
Доказательства теоремы можно найти в статьях Kjellström, 1970, и Kjellström & Taxén, 1981.
Поскольку дисперсия определяется как экспонента энтропии / беспорядка / средней информации, немедленно следует, что теорема верна также для этих концепций. В целом это означает, что гауссовская адаптация может выполнять одновременную максимизацию урожайности и средней информации (без какой-либо необходимости в определении урожайности или средней информации как критериальных функций).
Теорема верна для всех областей приемлемости и всех гауссовых распределений . Его можно использовать путем циклического повторения случайных вариаций и отбора (как естественная эволюция). В каждом цикле отбирается достаточно большое количество точек с распределением по Гауссу, которые проверяются на принадлежность к области приемлемости. Затем центр тяжести гауссианы m перемещается в центр тяжести утвержденных (выбранных) точек m *. Таким образом, процесс сходится к состоянию равновесия, удовлетворяющему теореме. Решение всегда является приблизительным, поскольку центр тяжести всегда определяется для ограниченного числа точек.
Впервые он был использован в 1969 году как чистый алгоритм оптимизации, делающий области приемлемости все меньше и меньше (по аналогии с моделированием отжига , Киркпатрик, 1983). С 1970 года он используется как для обычной оптимизации, так и для максимизации доходности.
Естественная эволюция и гауссовская адаптация
Его также сравнивали с естественной эволюцией популяций живых организмов. В этом случае s ( x ) - это вероятность того, что особь, имеющая массив x фенотипов, выживет, дав потомство следующему поколению; определение индивидуальной приспособленности, данное Хартлом 1981. Выход, P , заменяется средней приспособленностью, определенной как среднее по набору индивидуумов в большой популяции.
Фенотипы часто распределены по Гауссу в большой популяции, и необходимое условие для того, чтобы естественная эволюция могла выполнить теорему гауссовской адаптации в отношении всех гауссовских количественных признаков, состоит в том, что она может подтолкнуть центр тяжести гауссиана к центр тяжести выбранных особей. Это может быть выполнено с помощью закона Харди – Вайнберга . Это возможно, потому что теорема гауссовой адаптации действительна для любой области приемлемости, независимо от структуры (Kjellström, 1996).
В этом случае правила генетической изменчивости, такие как кроссовер, инверсия, транспозиция и т. Д., Могут рассматриваться как генераторы случайных чисел для фенотипов. Таким образом, в этом смысле гауссовская адаптация может рассматриваться как генетический алгоритм.
Как подняться на гору
Среднее приспособление может быть вычислено при условии, что известно распределение параметров и структура ландшафта. Реальный ландшафт неизвестен, но на рисунке ниже показан вымышленный профиль (синий) ландшафта вдоль линии (x) в комнате, охватываемой такими параметрами. Красная кривая - это среднее значение на основе красной колоколообразной кривой в нижней части рисунка. Его получают, позволяя кривой колокола скользить по оси x , вычисляя среднее значение в каждом месте. Как видно, сглаживаются небольшие пики и ямки. Таким образом, если эволюция начинается в точке A с относительно небольшой дисперсией (красная колоколообразная кривая), то подъем будет происходить на красной кривой. Процесс может застрять на миллионы лет в точках B или C, пока остаются пустоты справа от этих точек, а скорость мутаций слишком мала.
Если частота мутаций достаточно высока, беспорядок или дисперсия могут увеличиваться, и параметр (параметры) могут стать распределенными, как зеленая кривая колокола. Далее подъем будет происходить по зеленой кривой, которая еще более сглаживается. Поскольку впадины справа от B и C теперь исчезли, процесс может продолжаться вплоть до пиков в D. Но, конечно, ландшафт ограничивает беспорядок или изменчивость. Кроме того, в зависимости от ландшафта, процесс может стать очень прерывистым, и если соотношение между временем, проведенным процессом на локальном пике, и временем перехода к следующему пику очень велико, он также может выглядеть как пунктирный равновесие, предложенное Гулдом (см. Ридли).
Компьютерное моделирование гауссовой адаптации
Пока что теория рассматривает только средние значения непрерывных распределений, соответствующих бесконечному числу людей. В действительности, однако, количество людей всегда ограничено, что приводит к неопределенности в оценке m и M (матрица моментов гауссианы). И это тоже может сказаться на эффективности процесса. К сожалению, об этом известно очень мало, по крайней мере, теоретически.
Реализация нормальной адаптации на компьютере - довольно простая задача. Адаптация m может выполняться по одной выборке (индивидууму) за раз, например
- m ( i + 1) = (1 - a ) m ( i ) + ах
где x - это пройденный образец, а a <1 - подходящая константа, так что величина, обратная a, представляет количество особей в популяции.
В принципе, M может обновляться после каждого шага y, ведущего к допустимой точке.
- x = m + y согласно:
- M ( i + 1) = (1-2 b ) M ( i ) + 2 byy T ,
где y T - транспонирование y, а b << 1 - другая подходящая константа. Чтобы гарантировать подходящее увеличение средней информации , y должен быть нормально распределен с матрицей моментов μ 2 M , где скаляр μ > 1 используется для увеличения средней информации ( информационной энтропии , беспорядка, разнообразия) с подходящей скоростью. Но M никогда не будет использоваться в расчетах. Вместо этого мы используем матрицу W , определяемую WW T = M .
Таким образом, y = Wg , где g нормально распределена с матрицей моментов μU , а U - единичная матрица. W и W T могут быть обновлены по формулам
- W = (1 - b ) W + byg T и W T = (1 - b ) W T + bgy T
потому что умножение дает
- M = (1-2 b ) M + 2 byy T ,
где члены, включающие b 2 , не учитывались. Таким образом, M будет косвенно адаптирован с хорошим приближением. На практике достаточно обновить только W.
- Вт ( я + 1) = (1 - б ) W ( я ) + BYG Т .
Это формула, используемая в простой двухмерной модели мозга, удовлетворяющей правилу ассоциативного обучения Хебба; см. следующий раздел (Kjellström, 1996 и 1999).
На рисунке ниже показан эффект увеличения средней информации в гауссовском PDF, используемом для восхождения на гору Крест (две линии представляют собой контурную линию). И красный, и зеленый кластеры имеют одинаковую среднюю пригодность, около 65%, но зеленый кластер имеет гораздо более высокую среднюю информацию, что делает зеленый процесс намного более эффективным. Эффект от этой адаптации не очень заметен в двумерном случае, но в многомерном случае эффективность процесса поиска может быть увеличена на много порядков.
Эволюция в мозгу
Предполагается, что в мозгу эволюция ДНК-сообщений должна быть заменена эволюцией сигнальных паттернов, а фенотипический ландшафт заменен ментальным ландшафтом, сложность которого вряд ли будет второстепенной. Метафора с ментальным ландшафтом основана на предположении, что определенные паттерны сигналов способствуют улучшению самочувствия или производительности. Например, управление группой мышц приводит к лучшему произношению слова или исполнению музыкального произведения.
В этой простой модели предполагается, что мозг состоит из взаимосвязанных компонентов, которые могут складывать, умножать и задерживать значения сигналов.
- Ядро нервной клетки может добавлять значения сигнала,
- синапс может размножаться с постоянным и
- Аксон может задерживать значения.
Это основа теории цифровых фильтров и нейронных сетей, состоящих из компонентов, которые могут складывать, умножать и задерживать значения сигналов, а также многих моделей мозга, Levine 1991.
На рисунке ниже предполагается, что ствол мозга доставляет гауссовские паттерны сигналов. Это возможно, поскольку определенные нейроны срабатывают случайным образом (Кандел и др.). Ствол также представляет собой неупорядоченную структуру, окруженную более упорядоченными оболочками (Bergström, 1969), и согласно центральной предельной теореме сумма сигналов от многих нейронов может быть распределена по Гауссу. Треугольные прямоугольники представляют синапсы, а прямоугольники со знаком + - ядра клеток.
Предполагается, что сигналы коры головного мозга будут проверены на осуществимость. Когда сигнал принят, контактные области в синапсах обновляются в соответствии с приведенными ниже формулами в соответствии с теорией Хебба. На рисунке показано 2-мерное компьютерное моделирование гауссовой адаптации в соответствии с последней формулой в предыдущем разделе.
m и W обновляются в соответствии с:
- м 1 = 0,9 м 1 + 0,1 х 1; м 2 = 0,9 м 2 + 0,1 х 2 ;
- ш 11 = 0,9 ш 11 + 0,1 у 1 г 1 ; ш 12 = 0,9 ш 12 + 0,1 у 1 г 2 ;
- ш 21 = 0,9 ш 21 + 0,1 у 2 г 1 ; ш 22 = 0,9 ш 22 + 0,1 у 2 г 2 ;
Как можно видеть, это очень похоже на маленький мозг, управляемый теорией обучения Хебба (Kjellström, 1996, 1999 и 2002).
Гауссовская адаптация и свобода воли
Гауссовская адаптация как эволюционная модель мозга, подчиняющаяся теории ассоциативного обучения Хебба, предлагает альтернативный взгляд на свободную волю из-за способности процесса максимизировать среднюю приспособленность сигнальных паттернов в мозгу, взбираясь на ментальный ландшафт по аналогии с фенотипом. эволюция.
Такой случайный процесс дает нам большую свободу выбора, но почти никакой. Однако иллюзия воли может проистекать из способности процесса максимизировать среднюю приспособленность, заставляя процесс стремиться к цели. То есть он предпочитает более высокие пики ландшафта более низким или лучшие альтернативы перед худшими. Так может появиться призрачная воля. Аналогичное мнение высказал Зохар 1990. См. Также Kjellström 1999.
Теорема эффективности случайного поиска
Эффективность гауссовской адаптации основана на теории информации Клода Э. Шеннона (см. Информационное содержание ). Когда событие происходит с вероятностью P , может быть получена информация -log ( P ). Например, если средняя приспособленность P , информация , полученная для каждого человека , выбранную для выживания будет -log ( P ) - в среднем - и работы / время , необходимое для получения информации пропорционально 1 / P . Таким образом, если эффективность, E, определяется как информация, деленная на работу / время, необходимое для ее получения, мы имеем:
- E = - P log ( P ).
Эта функция достигает максимума при P = 1 / e = 0,37. Тот же результат был получен Гейнсом другим методом.
E = 0, если P = 0, для процесса с бесконечной скоростью мутации, и если P = 1, для процесса со скоростью мутации = 0 (при условии, что процесс жив). Этот показатель эффективности применим для большого класса процессов случайного поиска при соблюдении определенных условий.
1 Поиск должен быть статистически независимым и одинаково эффективным по различным направлениям параметров. Это условие может быть приблизительно выполнено, когда матрица моментов гауссиана была адаптирована для получения максимальной средней информации в некоторой области приемлемости, поскольку линейные преобразования всего процесса не влияют на эффективность.
2 Все люди имеют равную стоимость, а производная при P = 1 <0.
Тогда может быть доказана следующая теорема:
Все меры эффективности, которые удовлетворяют указанным выше условиям, асимптотически пропорциональны - P log ( P / q ) при увеличении количества измерений и максимизируются с помощью P = q exp (-1) (Kjellström, 1996 и 1999).
На рисунке выше показана возможная функция эффективности для процесса случайного поиска, такого как гауссовская адаптация. Слева процесс наиболее хаотичен, когда P = 0, в то время как справа есть идеальный порядок, когда P = 1.
В примере Rechenberg, 1971, 1973, случайное блуждание проталкивается через коридор, максимизируя параметр x 1 . В этом случае область приемлемости определяется как ( n - 1) -мерный интервал в параметрах x 2 , x 3 , ..., x n , но значение x 1 ниже последнего принятого никогда не будет принято. Поскольку в этом случае P никогда не может превышать 0,5, максимальная скорость в направлении более высоких значений x 1 достигается при P = 0,5 / e = 0,18, что согласуется с выводами Рехенберга.
Точка зрения, которая также может представлять интерес в этом контексте, заключается в том, что для доказательства теоремы не требуется никакого определения информации (кроме того, что точки выборки внутри некоторой области приемлемости не дают информации о ее расширении). Затем, поскольку формулу можно интерпретировать как информацию, разделенную на работу, необходимую для получения информации, это также указывает на то, что −log ( P ) является хорошим кандидатом на роль меры информации.
Алгоритм Штауффера и Гримсона
Гауссова адаптация также использовалась для других целей, например, для удаления тени с помощью «алгоритма Штауффера-Гримсона», который эквивалентен гауссовой адаптации, использованной в разделе «Компьютерное моделирование гауссовой адаптации» выше. В обоих случаях метод максимального правдоподобия используется для оценки средних значений путем адаптации по одной выборке за раз.
Но есть отличия. В случае Штауффера-Гримсона информация не используется для управления генератором случайных чисел для центрирования, максимизации средней пригодности, средней информации или производственного выхода. Адаптация матрицы моментов также сильно отличается от «эволюции в мозгу», описанной выше.
Смотрите также
Рекомендации
- Бергстрем, Р.М. Энтропийная модель развивающегося мозга. Психобиология развития , 2 (3): 139–152, 1969.
- Брукс, Д. Р. и Уайли, Э. О. Эволюция как энтропия, К единой теории биологии . Издательство Чикагского университета, 1986.
- Брукс, Д. Р. Эволюция в информационную эпоху: новое открытие природы организма. Семиозис, Эволюция, Энергия, Развитие, Том 1, номер 1, март 2001 г.
- Гейнс, Брайан Р. Управление знаниями в обществах интеллектуальных адаптивных агентов. Журнал интеллектуальных информационных систем 9, 277–298 (1997).
- Хартл, Д.Л. Учебник по популяционной генетике . Синауэр, Сандерленд, Массачусетс, 1981.
- Гамильтон, WD. 1963. Эволюция альтруистического поведения. Американский натуралист 97: 354–356
- Кандел, Э. Р., Шварц, Дж. Х., Джессел, Т. М. Основы неврологии и поведения . Prentice Hall International, Лондон, 1995.
- С. Киркпатрик, С. Д. Гелатт и М. П. Векки, Оптимизация путем моделирования отжига, Science, Vol 220, Number 4598, pages 671–680, 1983.
- Кьельстрём, Г. Оптимизация сети путем случайного изменения значений компонентов. Ericsson Technics , т. 25, нет. 3. С. 133–151, 1969.
- Кьельстрём, Г. Оптимизация электрических сетей с учетом допустимых затрат. Ericsson Technics , нет. 3. С. 157–175, 1970.
- Кьельстрём, Г. и Таксен, Л. Стохастическая оптимизация в проектировании систем. IEEE Trans. на Circ. и Syst., vol. КАС-28, вып. 7 июля 1981 г.
- Кьельстрём Г., Таксен Л. и Линдберг П.О. Дискретная оптимизация цифровых фильтров с использованием гауссовой адаптации и минимизации квадратичной функции. IEEE Trans. на Circ. и Syst., vol. CAS-34, № 10, октябрь 1987 г.
- Кьельстрём, Г. Об эффективности гауссовой адаптации. Журнал теории оптимизации и приложений , вып. 71, нет. 3 декабря 1991 г.
- Кьельстрём, Г. и Таксен, Л. Гауссовская адаптация, эффективный глобальный оптимизатор, основанный на эволюции; Вычислительная и прикладная математика, Ин, К. Брезинский и У. Кулиш (редакторы), Elsevier Science Publishers BV, стр. 267–276, 1992.
- Кьельстрём, Г. Эволюция как алгоритм статистической оптимизации. Эволюционная теория 11: 105–117 (январь 1996 г.).
- Кьельстрём, Г. Эволюция мозга. Прикладная математика и вычисления , 98 (2–3): 293–300, февраль 1999 г.
- Кьельстрём, Г. Эволюция в двух словах и некоторые следствия, касающиеся оценок. EVOLVE, ISBN 91-972936-1-X , Стокгольм, 2002.
- Левин, Д.С. Введение в нейронное и когнитивное моделирование. Лоуренс Эрлбаум Ассошиэйтс, Инк., Издательство, 1991.
- Маклин, П. Д. Триединая концепция мозга и поведения . Торонто, Univ. Торонто Пресс, 1973.
- Мейнард Смит, Дж. 1964. Групповой отбор и родственный отбор, Nature 201: 1145–1147.
- Мэйнард Смит, Дж. Эволюционная генетика . Издательство Оксфордского университета, 1998.
- Майр, Э. Что такое эволюция . Основные книги, Нью-Йорк, 2001.
- Мюллер, Кристиан Л. и Сбальзарини Иво Ф. Возвращение к гауссовской адаптации - энтропийный взгляд на адаптацию ковариационной матрицы. Институт теоретической информатики и Швейцарский институт биоинформатики , ETH Zurich , CH-8092 Zurich, Switzerland.
- Пинель, Дж. Ф. и Сингхал, К. Статистическое проектирование, центрирование и допуски с использованием параметрической выборки. IEEE Transactions on Circuits and Systems, Vol. Дас-28, № 7, июль 1981 г.
- Рехенберг И. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (докторская диссертация). Перепечатано Фромман-Хольцбугом (1973).
- Ридли, М. Эволюция . Blackwell Science, 1996.
- Stauffer, C. & Grimson, WEL Learning Patterns of Activity Using Real-Time Tracking, IEEE Trans. на ПАМИ, 22 (8), 2000.
- Стир Г. Об исследовании возможностей аналоговых интегральных схем в космосе. Технический университет Мюнхена, Диссертация 2005.
- Таксен, Л. Структура координации развития сложных систем. Технологический институт Университета Линчёпинга, диссертация, 2003.
- Зохар, Д. Квантовое Я: революционный взгляд на человеческую природу и сознание, основанный на новой физике . Лондон, Блумсбери, 1990.