Теория доказательства Демпстера-Шафера.

Альтернативный подход, называемый теорией обоснования Демпстера-Шафера, рассматривает множества предположений и ставит в соответствие каждому из них вероятностный интервал доверия (правдоподобия), которому должна принадлежать степень уверенности в каждом предположении. Мера доверия обозначается bel(p) и изменяется от нуля, что указывает на отсутствие свидетельств в пользу множества предположений, до единицы, означающей определенность. Мера правдоподобия предположения р - pl(p) определяется следующим образом:

pl(p) = 1 - bel(not(p)).

Таким образом, правдоподобие также изменяется от нуля до единицы и вычисляется на основе меры доверия предположению not(p). Если not(p) вполне обоснованно, то bel(not(p))= 1, a pl(p) равно 0. Единственно возможным значением для bel(p) также является нуль. Предположим, что существуют две конкурирующие гипотезы и h2 При отсутствии информации, поддерживающей эти гипотезы, мера доверия и правдоподобия каждой из них принадлежат отрезку [ 0; 1 ]. По мере накопления информации эти интервалы будут уменьшаться, а доверие гипотезам - увеличиваться. Согласно байесовскому подходу (при отсутствии свидетельств) априорные вероятности распределяются поровну между двумя гипотезами: Р (hi)=0,5. Подход Демпстера-Шафера также подразумевает это. С другой стороны, байесовский подход может привести к такой же вероятностной мере независимо от количества имеющихся данных. Таким образом, подход Демпстера-Шафера может быть очень полезен, когда необходимо принимать решение на основе накопленных данных. Итак, подход Демпстера-Шафера решает проблему измерения достоверности, делая коренное различие между отсутствием уверенности и незнанием. В теории вероятностей мы вынуждены выражать степень нашего знания о гипотезе h единственным числом P(h).Функция доверия Демпстера-Шафера удовлетворяет аксиомам, которые слабее аксиом теории вероятности, и сводится к теории вероятности, если все вероятности известны. Функции доверия позволяют использовать имеющиеся знания для ограничения вероятностей событий при отсутствии точных значений вероятностей. Теория Демпстера-Шафера основана на двух идеях. Первая- получение степени доверия для данной задачи из субъективных свидетельств о связанных с ней проблемах, и вторая - использование правила объединения свидетельств, если они основаны на независимых атомах.

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

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

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

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

Допустим нам нужно оптимизировать некоторую функцию F(X1,X2,..,Xn). Пусть мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать, как мы будем хранить решения. По сути, нам нужно поместить все X1-Xn в некоторый вектор, который будет играть роль хромосомы. Один из наиболее распространенных способов - кодировать значения переменных в битовом векторе. Например, выделим каждому иксу по 8 бит. Тогда наш вектор будет длины L=8*n. Для простоты будем считать, что биты лежат в массиве X[0..L-1].

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

Тогда ГА будет состоять из следующих шагов:

1.Генерация начальной популяции - заполнение популяции особями, в которых элементы массива X (биты) заполнены случайным образом.

2.Выбор родительской пары - берем K особей с максимальными значениями функции F и составляю из них все возможные пары (K*(K-1)/2). Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции

3.Кроссинговер - берем случайную точку t на массиве X (0..L-1).

Теперь, все элементы массива с индексами 0-t новой особи (потомка) заполняем элементами с теми же индексами, но из массива X первой родительской особи. Остальные элементы заполняются из массива второй родительской особи. Для второго потомка делается наоборот - элементы 0-t берут от второго потомка, а остальные - от первого.

4.Новые особи с некоторой вероятностью мутируют - инвертируется случайный бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.

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

6.Если самое лучшее решение в популяции нас не удовлетворяет, то переход на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются бесконечно.

Преимущества

Они не требуют никакой информации о поверхности ответа;

Разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;

Они стойки к попаданию в локальные оптимумы;

Они хорошо работают при решении крупномасштабных проблем оптимизации;

Могут быть использованы для широкого класса задач;

Просты и прозрачны в реализации;

Могут быть использованы в задачах с изменяющейся средой.

НедостаткиНе желательно и проблематично использовать ГА:

В случае когда необходимо найти точный глобальный оптимум;

Время исполнения функции оценки велико;

Необходимо найти все решения задачи, а не одно из них;