Машинное обучение: введение в генетические алгоритмы

Переводчик: Хаоминг

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

Introduction to ""Machine Learning in Javascript""Этот блог дает хорошее введение и контекст для этого блога и других блогов в этой серии.

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

Выше я употребил очень важный термин «универсальный». Для любой заданной вычислительной задачи вы, вероятно, найдете алгоритм, который решает ее более эффективно, чем ГА. Но решение конкретных вычислительных задач не является целью ни этого упражнения, ни ГА. Вы хотите использовать GA не потому, что у вас есть сложная проблема, а потому, что у вас есть сложная проблема, связанная с несколькими проблемами. В качестве альтернативы вы можете использовать GA, когда у вас есть сложный, но нерелевантный набор параметров.

Одно приложение, которое приходит мне на ум, — это функция ходьбы двуногого робота. Заставить робота ходить на двух ногах очень сложно. Жесткое программирование программы ходьбы почти наверняка потерпит неудачу. Даже если вам удастся заставить одного робота ходить, у следующего другого робота может быть немного другой центр баланса, и алгоритм, который вы поработили, больше не будет работать. Чтобы не страдать от неизбежного горя, вы должны использовать GA, чтобы «научить робота ходить» вместо того, чтобы просто «научить робота ходить»».

Давайте реализуем GA на JavaScript.

проблема

Создайте программу генетического алгоритма на JavaScript для генерации текста «Hello, World!».

Естественно, все начинается с «Hello, World!», поэтому создание программы GA, которая выдает эту фразу, также уместно. Обратите внимание, что это очень надуманный вопрос. В какой-то момент мы даже напечатали в исходном коде фразу «Hello, World!»! Кажется глупым вообще писать алгоритм, если вы знаете желаемый результат. Ответ прост, это упражнение для обучения. Следующее упражнение GA (которое будет основано на PHP) будет менее замысловатым, но мы начнем с другого.

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

Основной метод ГА состоит в том, чтобы сгенерировать группу «решений-кандидатов», а затем использовать некоторую обратную связь для расчета того, насколько решения-кандидаты близки к оптимальному решению. Далекий от оптимального вариант решения буквально умирает, и больше его никто не видит. Решения-кандидаты, близкие к оптимальному, комбинируются друг с другом и могут немного видоизменяться; это попытка время от времени корректировать решение-кандидат и посмотреть, ближе или дальше решение-кандидат от оптимального решения.

Эти «варианты решения» называются **~~Ген~~хромосома**. (Примечание: терминология, которую я использую здесь~~Ген~~это не правильно. Технически гены — это отдельные признаки решения-кандидата, а целое называется хромосомой. Семантика важна!)

Спаривание хромосом дает потомство, которое затем мутирует. Они либо умирают по закону выживания наиболее приспособленных, либо им позволяют производить потомство с более желательными характеристиками, приспособленными к естественному отбору.

Это может быть странным способом думать о решении проблемы «Hello, World!», но придерживайтесь его. Этот пример — не единственная проблема, которую могут решить ГА.

хромосома

Моделью решения является хромосома, в нашем случае сама хромосома является строкой. Предположим, что все хромосомы имеют длину 13 символов (например, «Hello, World!»). Вот некоторые возможные хромосомы, которые могут быть кандидатами на решение проблемы:

Gekmo+ xosmd!
Gekln, worle""
Fello, wosld!
Gello, wprld!
Hello, world!

Очевидно, что последняя является правильной (или глобально оптимальной) хромосомой. Но как мы оцениваем оптимальность хромосом?

функция стоимости

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

В этом случае мы можем определить функцию стоимости следующим образом:

Для каждого символа в строке вычислите разницу между символом-кандидатом и целевым символом в представлении ASCII, а затем возведите разницу в квадрат, чтобы «стоимость» всегда была положительной.

Например, если у нас есть заглавная буква «А» (ASCII 65), но предполагается, что это заглавная буква «С» (ASCII 67), то наша стоимость этого символа равна 4 (67 - 65 = 2, 2^2 = 4).

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

Используя приведенное выше правило в качестве функции стоимости, мы можем рассчитать стоимость (в скобках) для 5 приведенных выше примеров хромосом:

Гекмо+ xosmd!(7)
Гекльн, мир""(5)
Привет, мир!(5)
Привет, wprld!(2)
Привет мир!(0)

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

Функция стоимости — очень важный аспект ГА, потому что, если вы достаточно сообразительны, вы можете использовать ее для согласования _совершенно несвязанных параметров_. В нашем случае мы просто смотрим на буквы. Но что, если вы создаете приложение для навигации по вождению и вам нужно сопоставить плату за проезд, светофоры, плохие районы и мосты? Это совершенно не связанные параметры, но вы можете свести их к аккуратной функции стоимости, применив к каждому параметру разные веса.

подбери и умри

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

Мы не говорили о «популяции» в ГА (мы обсудим это позже), но сейчас я просто говорю, что когда вы запускаете ГА, вы не видите только одну хромосому за раз. Все ваше население одновременно может составлять 20, 100 или 5000 человек. Подобно эволюции, ожидая, что потомство будет более здоровым, чем любой из родителей, вы можете быть склонны скрещивать друг с другом самые лучшие и сильные хромосомы в популяции.

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

Возьмите эти две строки в качестве примера:

Привет мир!(1)
Привет, мир!(1)

Разрезая их посередине, а затем взаимодействуя пополам, мы получаем этих двух новых «потомков»:

Привет, впрлд!(2)
Привет мир!(0)

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

Спаривание — это то, как гены передаются следующему поколению.

мутация

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

(Недавно мне сказали, что приведенный выше абзац немного вводит в заблуждение. У некоторых читателей создается впечатление, что наиболее важным аспектом хромосомной эволюции является спаривание, и что на практике ГА не даст очень незначительного результата, если не сочетает спаривание и мутацию. Мутации помогают нам находить более оптимальные решения из предыдущих превосходных решений [решения многих проблем, таких как наш пример Hello World, можно разделить на оптимальные подрешения, такие как ""Hello"" и """World""], но только мутации может продвинуть поиск решений в новых направлениях.)

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

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

Здесь мы проиллюстрируем это примером. Допустим, у нас есть эти две хромосомы:

Hfllp, worlb!
Hfllp, worlb!

Опять надуманный пример, но бывает. Ваши две хромосомы одинаковы. Это означает, что их дети, как и их родители, не будут прогрессировать. Но если в одной из 100 хромосом есть случайная мутация одного символа, это только вопрос времени, когда хромосома № 2 выше станет «Illp, world!». Затем эволюция продолжится, потому что ребенок в конце концов снова будет отличаться от родителя. Мутация продвигает эволюцию вперед.

Как и когда мутировать зависит от вас. Опять же, проведите экспериментальное исследование. Код, который я дам вам позже, имеет очень высокую частоту мутаций (50%), но это просто для галочки. Вы можете сделать его ниже, скажем, на 1%. В моем коде всего _одна буква_сдвиг_одна кодовая точка ASCII_, но вы можете сделать свой код немного более агрессивным. Экспериментируйте, тестируйте и учитесь. Это единственный способ.

Хромосомы: резюме

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

Мне нравится думать об этих вещах в терминах ООП. Таким образом, класс «хромосома» обладает следующими свойствами:

Атрибуты:

генетический код
стоимость/фитнес

метод:

пара
мутация
Рассчитать пригодность

Теперь мы посмотрим, как взаимодействуют гены в последней части головоломки ГА: «популяция».

Население

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

Вы можете выбрать свой собственный размер населения. Я выбрал 20 для своей программы ниже, но вы можете выбрать 10, 100 или 10000, если хотите. У них есть преимущества и недостатки, но, как я уже много раз говорил: проведите эксперимент сами и изучите его!

Популяции проходят через «поколения». Типичное поколение может состоять из них:

Рассчитать показатели стоимости/пригодности для каждой хромосомы
Сортировка хромосом по стоимостной стоимости/показатель пригодности
Убейте определенное количество самых слабых членов — вы выбираете количество хромосом, которые умрут.
Соедините определенное количество сильнейших участников — опять же, вы сами выбираете, как это сделать.
член случайной мутации
Какой-то тест на здравомыслие — например, как определить, что проблема считается «решенной»?

начать и закончить

Инициализировать популяцию легко. Просто заполните его совершенно случайными хромосомами. В нашем случае оценка стоимости совершенно случайной строки — _ужасно_. Наш код начинается со средней стоимости 30000. Но это нормально — для этого и нужна эволюция. Вот почему мы здесь.

Знать, когда остановить эволюцию популяции, немного сложно. Сегодняшний пример очень прост: остановитесь, когда вы получите 0 стоимости. Но это не всегда так. Иногда вы не знаете наименьшее доступное значение себестоимости. Или, если вы используете значения пригодности вместо значений стоимости, вы можете не знать максимально возможное значение пригодности.

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

Остановите алгоритм, если лучший результат не изменился за 1000 поколений, затем используйте его в качестве ответа.

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

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

код

Наконец! Мне нравится подход ООП, но мне также нравится грубый и простой код, поэтому я стараюсь писать этот код как можно более прямолинейно, хотя он может быть немного грубым на границе.

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

var Gene = function(code) {  
        if (code)
                this.code = code;
        this.cost = 9999;
};
Gene.prototype.code = '';  
Gene.prototype.random = function(length) {  
        while (length--) {
                this.code += String.fromCharCode(Math.floor(Math.random()*255));
        }
};

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

Gene.prototype.calcCost = function(compareTo) {  
        var total = 0;
        for(i = 0; i < this.code.length; i++) {
                total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i));
        }
        this.cost = total;
};

Функция стоимости принимает в качестве аргумента строку «имитация», находит их разницу в кодовых точках и возводит ее в квадрат.

Gene.prototype.mate = function(gene) {  
        var pivot = Math.round(this.code.length / 2) - 1;

        var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot);
        var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

        return [new Gene(child1), new Gene(child2)];
};

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

Gene.prototype.mutate = function(chance) {  
        if (Math.random() > chance)
                return;

        var index = Math.floor(Math.random()*this.code.length);
        var upOrDown = Math.random()

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

var Population = function(goal, size) {  
        this.members = [];
        this.goal = goal;
        this.generationNumber = 0;
        while (size--) {
                var gene = new Gene();
                gene.random(this.goal.length);
                this.members.push(gene);
        }
};

Конструктор класса популяции принимает в качестве аргументов целевую строку и размер популяции, а затем заполняет популяцию случайными хромосомами.

Population.prototype.sort = function() {  
        this.members.sort(function(a, b) {
                return a.cost - b.cost;
        });
}

Я определил метод Population.prototype.sort как вспомогательную функцию для сортировки населения по стоимости.

Population.prototype.generation = function() {  
        for (var i = 0; i < this.members.length; i++) {
                this.members[i].calcCost(this.goal);    
        }

        this.sort();
        this.display();
        var children = this.members[0].mate(this.members[1]);
        this.members.splice(this.members.length - 2, 2, children[0], children[1]);

        for (var i = 0; i < this.members.length; i++) {
                this.members[i].mutate(0.5);
                this.members[i].calcCost(this.goal);
                if (this.members[i].code == this.goal) { 
                        this.sort();
                        this.display();
                        return true;
                }
        }
        this.generationNumber++;
        var scope = this;
        setTimeout(function() { scope.generation(); } , 20);
};

Самый толстый популяционный метод — это метод поколений. Здесь нет никакой магии. Функция display() (которая не отображается на странице) просто отображает вывод на страницу, и я установил паузу между поколениями, чтобы система не взорвалась.

Обратите внимание, что в этом примере я соединил только две самые сильные хромосомы. Ваш метод не должен быть таким.

window.onload = function() {  
        var population  = new Population(""Hello, world!"", 20);
        population.generation();
};

Приведенный выше код включает систему, посмотрите на практике.

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

Обратите внимание, что нет ничего, что нельзя было бы сделать на _других_ языках программирования. Но вы могли ожидать и этого, потому что в конце концов это «машинное обучение на всех языках».

Приятного обучения! Следующий блог в этой серии — [ML in JS: k-nearest-neighbor](С таким же успехом можно заглянуть на bill.com/blog/marchinei… ""Machine Learning in JS: k-nearest-neighbor Introduction"").

Существует также [Генетические алгоритмы, часть 2] (С таким же успехом можно заглянуть на bill.com/blog/marchinei…««Машинное обучение: генетические алгоритмы в Javascript, часть 2»»), вы должны прочитать его, если хотите углубиться.