Алгоритмы *

Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

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

Кому интресно, прошу под кат.

При работе с текстом часто возникает потребность корректно расставить переносы. Задача на первый взгляд не такая уж очевидная, нужно учитывать особенности каждого языка, чтобы решить, в каком месте разорвать слово. Как правильно формализовать такие требования, и как потом применить их в алгоритме? Одно из самых распространенных на сей день решений предложил Франклин Марк Лян, студент известного профессора Дональда Кнута. Алгоритм так и называется – «Алгоритм Ляна-Кнута», он применяется в издательской системе TeX, автор которой опять же Д. Кнут.

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

Что удивительного в этой картинке?



На самом деле она уникальна. Матрица размером 17 х 17 раскрашена четырьмя цветами, при этом на ней нельзя построить ни единого (!) прямоугольника, чтобы все углы его были одного цвета. Имеются в виду прямоугольники любого размера с вершинами в разных точках и рёбрами, параллельными осям x и y.

Ниже перевод статьи Бо Аллена отсюда.

Простой наглядный пример

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

После публикации прошлой статьи, я полностью забил на попытку выполнить алгоритм при помощи HSV или Lab координат. Забил на использовании библиотек цветов и вообще на сам скрипт забил.

Но что-то стало скучно и опять зачесались руки поработать с изображениями и одновременно захотелось исправить уже имеющийся алгоритм.
Скрипт: link

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

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Давным-давно в 1637 году Пьер Ферма имел глупость написать на полях «Арифметики» Диофанта следующее: «… невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

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

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

Недавно сразу несколько достаточно авторитетных по местным меркам новостных порталов взорвала новость: Узбекский математик разгадал теорему Ферма — Математик из Ташкента Борис Пономарев утверждает, что отыскал «простое оригинальное доказательство» Великой теоремы Ферма — загадки, над которой ученые всего мира бьются вот уже 350 лет (например, здесь, здесь и здесь). В одной из них даже было приведено доказательство.

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

• есть некоторое количество (можно считать, что не более 16 миллионов) измерений набора параметров. Число параметров в наборе – от 2 до 5.
• измерение параметров может быть относительно успешным – тогда их результат будет неподалеку от истинного (параметры и тип распределения неизвестны), либо не успешным – тогда результат будет случайным (опять-таки с неизвестными параметрами распределения). Определить по одиночному измерению, было ли оно успешным, нельзя.
• Можно считать, что точка сгущения существует. Если их несколько с близким качеством (которое формально так и не определяется), можно выдать любую.
• ответ нужно дать за один проход по исходным данным: перевычислять их или сохранять целиком – дорого.
• И, как обычно, хочется, чтобы алгоритм выглядел попроще, а работал побыстрее.

Задача о назначениях известна достаточно давно, основные алгоритмы ее решения уже описаны на Хабарахабре (см. например Задача о назначениях). Тем не менее задача до сих пор актуальна при распределении сотрудников по должностям, в случае когда сотрудников и должностей и критериев очень много, обычные методы окажутся очень трудоемкими
для лица, принимающего решение (ЛПР). Более того, на данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которю можно разбить на две задачи. Если вакансия одна, а претендентов много, то для ЛПР для выбора эффективным будет использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода (Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.).

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

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

К сожалению, большинство инструментов, которые применяются для вычислений, будут прятать результат, но если вы найдете такой, который этого (1/998001=1.002003004005006e-06) не делает, то, может, не сразу заметно, но деление 1 на 998001 дает в результате все числа от 001 до 999.

Если вам интересна такого рода математика, то 1/9801 выдаст похожий результат, последовательность чисел от 01 до 99

Можно посмотреть в WolframAlpha. Нажимайте «More digits» в блоке «Decimal approximation»:
www.wolframalpha.com/input/?i=1%2F998001
www.wolframalpha.com/input/?i=1%2F9801

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

На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.

Предыстория

Очень давно, когда мои познания в PHP были на уровне мат операций и вывода результатов, а нашел очень полезный класс, написанный Kalpeh Gamit, его сайт уже давно недоступен, поэтому, к сожалению контакты оставить не могу. Класс распространяется под именем GetImageColor и лицензией GPL 2.0.

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

Предыдущие части:

1. Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Часть 1/3: Теория
2. Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Реализация на Java. Часть 2/3: Основной алгоритм

Пример взят из книги: Борисов, Крумберг, Федоров — «Принятие решений на основе нечетких моделей. Примеры использования», 1990. Стр. 94-102

Условие. Руководство института рассматривает кандидатов на замещение вакантной должности на факультете. Задача заключается в том, чтобы, используя описанный выше метод, выявить наилучшеrо из них. Обсуждение среди членов факультета дало следующий результат:
d1: «Если кандидат опытный исследователь, имеет некоторый производственныи стаж и опыт преподавания технических дисциплин, то он удовлетворяющий (отвечающий требованиям)»;

d2: «Если он вдобавок к вышеописанным требованиям может преподавать теорию информационных систем, то он более чем удовлетворяющий»;
d3: «Если он вдобавок к условиям d2 имеет способпость найти заказчика наукоемкой продукции, то он безупречный»;

d4: «Если оп имеет все, oгoвopeннoe в d3, кроме способности преподавать теорию информационных систем, то он очень удовлетворяющий»;
d5: «Если кандидат очень опытный исследователь, имеет способность найти заказчика и хороший преподаватель, но не имеет производственноrо стажа, он все же будет удовлетворяющим»;
d6: «Если он не имеет квалификации исследователя или не имеет проверенной способности к преподаванию, он — неудовлетворяющий».

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

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

Однако всё, что удалось найти, — статьи на английском этого самого Тадао Такаоки (вот одна из этих статей). Пришлось переводить.

Сама идея алгоритма сначала казалась до безобразия простой:

Перед прочтением крайне рекомендую ознакомиться с первой частью статьи:
Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Часть 1/3: Теория

Для осуществления выбора необходим набор правил (интерфейс Rule), которе включают в себя набор соответствующих им нечетких логических функций (реализующих интерфейс Function) и определенные входные формализованные данные (изначально представляющие собой двухмерный массив элементов типа double).

Для бОльшего удобства данные (одномерные массивы элементов типа double) внутри класса Rule хранятся в классе-обертке Skill.

Далее правила передаются классу Facade, создающего из них нечеткие подмножества, размеры которых зависят от количества исследуемых объектов и требуемой точности (задаваемой в статическом классе Variables).

После нахождения общего функционального решения этой системы подмножеств (метод calcD) применяется процедура сравнения полученных нечетких подмножеств в единичном интервале для получения наилучшего решения (метод calcC); для этого вычисляются мощности данных уровневых множеств и их точечные оценки (метод calcS); в данном алгоритме для облегчения требуемой сортировки элементов применяется класс-структура Num.

Нечеткая логика — математические основы
Нечёткое множество

Описание метода
Пусть имеется множество элементов U, а A – его нечеткое подмножество, степень принадлежности его элементов определяется значением X, принимающим значение из интервала [0;1].
Таким образом, объект можно описать набором критериев(параметров) X(1), X(2) … X(n), принадлежащих соответствующим базовым множествам U(1), U(2) … U(n). Совокупность критериев с соответствующими значениями характеризует приемлимость S данного объекта относительно поставленной задачи.

Рассмотрим ситуацию, когда необходимо обрабатывать столкновения между объектами. Как вы в этом случае поступите? Вероятно, самым простым решением будет проверить каждый объект с каждым другим объектом. И это правильное решение, и все будет замечательно до тех пор пока объектов не много. Как только их станет порядка нескольких тысяч, вы заметите, что все стало как-то медленно работать. А если частиц несколько десятков тысяч или сотен? Тогда все замрет. Вот здесь уже интересно, на какие хитрости и оптимизации вы пойдете, чтобы решить такую проблему.

Для простоты, будем рассматривать 2D случай, частицы круглые, радиус частиц у всех одинаковый.

Содержание

1. Обзор алгоритмов
1.1. Полный перебор
1.2. Sweep & Prune
1.3. Регулярная сеть
2. Некоторые оптимизации
2.1. Sweep & Prune
2.2. Регулярная сеть
3. Сравнение скорости выполнения
4. Приложение (программа и исходный код)
5. Заключение