Многозначные логики. Их интерпретация и применение
Многозначная логика — это совокупность логических систем, опирающихся на принцип многозначности, в соответствии с которым всякое высказывание имеет одно (и только одно) из трёх или более истинностных значений. В зависимости от множества истинностных значений различают конечнозначные и бесконечнозначные логики.
Первыми логическими системами, опирающимися на принцип многозначности, были трёхзначная логика Ł3Я. Лукасевича (1920) и n-значная логика Э. Поста (1921), в которой высказываниям приписывались значения из конечного множества натуральных чисел 1, 2, … n, где n больше единицы и конечно.
Трехзначная система Лукасевнча.Трехзначная пропозициональная логика (логика высказыва ний) была построена в 1920 г. польским математиком и логи ком Я. Лукасевичем (1878-1956)'. В ней “истина” обозначает ся 1, “ложь” - 0, “нейтрально” – 1/2. В качестве основных функ ций взяты отрицание (Nx) и импликация (Сху);производными являются конъюнкция (Кху) и дизъюнкция (Аху). Тавтология принимает значение 1.
Отрицание и импликация соответственно определяются мат рицами (таблицами) так:
Импликация Лукасевича | |||
X \ y | 1/2 | ||
1/2 | |||
1/2 | l | 1/2 | |
l |
Отрицание Лукасевича
х | Nx |
1/2 | 1/2 |
[Nx] =1-[x] Конъюнкция определяется как минимум значений аргументов: [Кху] = min ( [х],[у]); дизъюнкция - как максимум значений х и у[Аху]=таx([х],[у]).
Трехзначная система Гейтинга.В двузначной логике из закона исключенного третьего выво дятся: 1) →х; 2) х
. Исходя из утверждения, что истин ным является лишь второе, нидерландский логик и математик А. Гейтинг (1898-1980) разработал трехзначную пропозицио нальную логику. В этой логической системе импликация и от рицание отличаются от определений этих операций у Лукасеви ча лишь в одном случае. “Истина” обозначается 1, “ложь” - 0, “неопределенность” -1/2. Тавтология принимает значение 1.
Импликация Гейтинга
x \ y | ? | ||
? | |||
? | |||
Отрицание Гейтинга
x | Nx |
? | |
Конъюнкция и дизъюнкция определяются обычным способом как минимум и максимум значении аргументов.
Если учитывать лишь значения функций 1 и 0, то из матриц системы Гейтинга вычленяются матрицы двузначной логики.
этой трехзначной логике закон непротиворечия является тавтологией, но ни закон исключенного третьего, ни его отрицание тавтологиями не являются. Оба правильных модуса условно-категорического силлогизма, формула (х → у) → (
), правила де Моргана и закон исключенного четвертого (x
)- тавтологии.
Хотя по сравнению с логикой Лукасевича в матрицах отрица ния и импликации Гейтингом в его системе были произведены небольшие изменения, результаты оказались значительными: в системе Гейтинга являются тавтологиями многие формулы классического двузначного исчисления высказываний.
т-значиая система Поста (Рт ). Система американского математика и логика Э. Л. Поста (1897- 1954) является обобщением двузначной логики, ибо при т = 2 в качестве частного случая мы получаем двузначную логику. Значения истинности суть 1, 2, ..., т (при т 2), где т -конечное число. Тавтологией является формула, которая всегда принимает выделенное значение, лежащее между 1 и т - 1, вклю чая их самих.
Пост вводит два вида отрицания (N1x и N2х) соответственно называемые циклическим и симметричным. Они определяются путем матриц и посредством равенств. Первое отрицание определяется двумя равенствами:
1. [N1x]=[x]+1 при [х] т-1; 2. [N1m]=1.
Второе отрицание определяется одним равенством: [N 2 x]=m-[x]+1
Характерной особенностью двух отрицаний Поста является то, что при т = 2 эти отрицания совпадают между собой и с отрицанием двузначной логики, что подтверждает тезис: многозначная система Поста есть обобщение двузначной логики.
Этапы развития логики как науки и основные направления современной символической логики
X | N 1x | N 2 x |
m | ||
m – 1 | ||
m –2 | ||
m – 3 | ||
. | . | . |
m – 1 | m | |
m |
Конъюнкция и дизъюнкция определяются соответственно как максимум и минимум значений аргументов. При указанных опре делениях отрицания, конъюнкции и дизъюнкции обнаруживается, что при значении для х, большем двух, законы непротиворечия и исключенного третьего, а также отрицание этих законов не явля ются тавтологиями.
Методологические проблемы применения многозначных логик для моделирования систем с наличием элемента неопределенности. (О применении многозначных логик в социологии).
Многозначные логики используются при моделировании систем с наличием элемента неопределенности. Простейшим при мером применения трехзначной логики является голосование:
“за”, “против”, “воздержался” или ответы на вопросы: “да”, “нет”, “затрудняюсь ответить”.
Более сложной методологической проблемой является применение многозначных логик при построении социологических анкет. Обычно дается ряд ответов на один вопрос. Ответы формулируются приблизительно так: “да”, “нет”, “скорее да, чем нет”, “ско рее нет, чем да”, “удовлетворен в значительной степени”, “мало удовлетворен” и т. д. Все эти ответы включают значительный элемент неопределенности, что затрудняет выявление мнения людей в ходе социологического опроса (или анкетирования).
Автор считает возможным использовать многозначные логики с различными значениями истинности, т. е., например, 6-ти, или 8-ми, или 9-ти, или 12-значные логики. Составляющий анкету соци олог должен предлагать конкретные значения истинности суждений, т. е. предусмотреть точные оценки, которые даст сам человек, рабо тающий с анкетой. Например, в 9-значнои логике значениями истинности будут следующие: 1,15/16,7/8,3/4,1/2 ,1/4 ,1/8, 1/16, 0.
Если человек, например, при ответе на вопрос: “Удовлетво рен ли он своим трудом?” им полностью удовлетворен, то в соответствующем разделе он напишет 1, если же он полностью не удовлетворен, то напишет значение 0. Если он почти удовле творен (согласен), то напишет либо 15/16 либо 7/8; если же он почти не удовлетворен, то напишет 1/16 или 1/8. Если он не знает ответа или думает неопределенно, то напишет 1/2.
При обработке информации на ЭВМ на основе данных число вых характеристик ответов можно получить более точные зна ния о мнении в репрезентативной выборке любого вида (стихий ной, квотной, вероятностной и других, когда применяется непол ная индукция) или во всей генеральной совокупности (т. е. при сплошном обследовании, когда применяется полная индукция).
Карты Кохонена.
Предложена Кохоненом в 1984 году. К настоящему времени существует множество модификаций исходной модели с богатой математической теорией вокруг них. В мозге нейроны располагаются в определенном порядке так, что некоторые внешние физические воздействия вызывают ответную реакцию нейронов из определенной области мозга. Например, в той части мозга, которая отвечает за восприятие звуковых сигналов, нейроны группируются в соответствии с частотами входного сигнала, на которых они резонируют. Хотя строение мозга в значительной степени предопределяется генетически, отдельные структуры мозга формируются в процессе самоорганизации. Алгоритм Кохонена в некоторой степени напоминает процессы, происходящие в мозге. Алгоритм Кохонена дает возможность строить нейронную сеть для разделения векторов входных сигналов на подгруппы. Сеть состоит из М нейронов, образующих прямоугольную решетку на плоскости. Элементы входных сигналов подаются на входы всех нейронов сети. В процессе работы алгоритма настраиваются синаптические веса нейронов. Входные сигналы - вектора действительных чисел - последовательно предъявляются сети. Желаемые выходные сигналы не определяются. После того, как было предъявлено достаточное число входных векторов, синаптические веса сети определяют кластеры. Кроме того, веса организуются так, что топологически близкие узлы чувствительны к похожим внешним воздействиям (входным сигналам). Для реализации алгоритма необходимо определить меру соседства нейронов (меру близости). Зоны соседства уменьшаются с течением времени. Алгоритм Кохонена формирования карт признаков:
1. Инициализация сети: Весовым коэффициентам сети присваиваются малые случайные значения. Общее число синаптических весов - M*N. Предъявление сети нового входного сигнала. Вычисление расстояния до всех нейронов сети. Выбор нейрона с наименьшим расстоянием. Производится подстройка весов для нейрона "победителя" и всех нейронов из его зоны соседства NE.
Возвращение к шагу 2. Области применения: кластерный анализ, распознавание образов, классификация. Сеть может быть использована для кластерного анализа только в том случае, если заранее известно число кластеров, В отличие от сети ART Гроссберга, сеть Кохонена способна функционировать в условиях помех, так как число классов фиксировано, веса модифицируются медленно, настройка весов заканчивается после обучения. Одна из модификаций состоит в том, что к сети Кохонена добавляется сеть MAXNET, которая определяет нейрон с наименьшим расстоянием до входного сигнала. Самоорганизу́ющаяся ка́рта Ко́хонена — нейронная сеть с обучением без учителя, выполняющая задачу визуализации и кластеризации. Идея сети предложена финским учёным Т. Кохоненом. Является методом проецирования многомерного пространства в пространство с более низкой размерностью (чаще всего, двумерное), применяется также для решения задач моделирования, прогнозирования и др. Является одной из версий нейронных сетей Кохонена. Самоорганизующиеся карты Кохонена используются для решения таких задач, как моделирование, прогнозирование, выявление наборов независимых признаков, сжатие информации, а также для поиска закономерностей в больших массивах данных. Наиболее часто описываемый алгоритм применяется для кластеризации данных.
21. Алгоритм интеллектуальной оптимизации «Пчелиный алгоритм».
Алгоритм пчел является довольно молодым алгоритмом для нахождения глобальных экстремумов (максимумов или минимумов) сложных многомерных функций. А также пчелиные алгоритмы используются для решения различных задач, возникающих при планировании производства, составлении графиков осмотра, хранения и транспортировке товаров и т.д., которые часто могут быть представлены как задачи теории графов, тесно связанные с «задачей раскраски». Данные задачи относят к классу NP-трудных задач, точное решение которых нельзя найти за разумное время, т.к. пространство поиска решений увеличивается в экспоненциальной зависимости от входных данных.
Алгоритм основан на поведении пчёл в естественной природной среде. Пчелиный алгоритм основан на методе поиска пчёлами элитных участков. Основное преимущество данного алгоритма – пчёлы исследуют также участки, находящиеся в окрестностях элитных, что позволяет, во-первых, разнообразить популяцию решений на последующих итерациях, во-вторых, приблизить решения к оптимальному.
Существует два основных алгоритма – пчелиный алгоритм (Bee Algorithm) и алгоритм колонии (роя) пчёл (Artificial Bee Colony).
Идея пчелиного алгоритма – сначала из улея вылетают в случайном направлении какое-то количество пчел-разведчиков, которые пытаются отыскать участки, где есть нектар. Через какое-то время пчелы возвращаются в улей и особым образом сообщают остальным пчелам, где и сколько они нашли нектара.
После этого на найденные участки отправляются другие пчёлы, причем, чем больше на данном участке предполагается найти нектара, тем больше пчел летит в этом направлении. А разведчики опять улетают искать другие участки, после чего процесс повторяется.
Формально простейший алгоритм пчёл можно представить следующим образом:
1º «создание пчёл»;
2º определение ЦФ (значения целевых функций) пчёл;
3º выбор участков для поиска;
4º отправка пчёл-разведчиков;
5º выбор пчёл с лучшими ЦФ;
6º отправка рабочих пчёл для случайного поиска и определение их ЦФ;
7º создание новой популяции пчёл;
8º до тех пор, пока условия выхода не выполнены, повторяем пункты 2-7.
Принцип работы алгоритма поведения роя пчёл, или метода роя пчёл (МРП): без какого-либо представления о поле априори, пчелы начинают поиск цветов со случайных позиций со случайными векторами скорости. Каждая пчела может помнить позиции, где она нашла наибольшее количество цветов и каким-то образом знать области, где другие пчелы обнаружили наибольшую плотность цветов. Выбирая между возвращением к месту, где пчела сама обнаружила наибольшее количество цветов, или исследованием места, определенного другими, как место с наибольшим количеством цветов, пчела устремляется в направлении между двумя точками в зависимости от того, что окажет большее влияние на ее решение – персональное воспоминание или социальный рефлекс. По пути пчела может найти место с более высокой концентрацией цветов, чем было найдено ранее. В дальнейшем оно может быть обозначено как новое место с наибольшей концентрацией цветов, а также как место наибольшего скопления цветов, найденное всем роем. Случайно пчела может пролететь мимо места, с большим количеством цветов, чем было найдено любой другой пчелой роя. Весь рой, затем будет стремиться навстречу этому месту в дополнении к собственным наблюдениям каждой пчелы. Таким образом, пчелы исследуют поле: перелетая места с наибольшей концентрацией, они замедляются в их направлении. Непрерывно они проверяют места, которые пролетели, сравнивая с найденными ранее местами с наибольшей концентрацией цветов надеясь найти абсолютную наибольшую концентрацию цветов. В конечном итоге, пчела заканчивает движение на месте поля с наибольшей концентрацией цветов. Вскоре весь рой сосредотачивается в окрестностях этой позиции. Не имея возможности обнаружить места с большей концентрацией цветов, пчелы непрерывно роятся в районе наибольшей плотности цветов. Это поведение пчёл роя и было положено в основу этого метода оптимизации.
Язык метода роя пчел. Каждая пчела в рое рассматривается как частица или агент. Все частицы роя действуют индивидуально в соответствии с одним управляющим принципом: ускоряться в направлении наилучшей персональной и наилучшей общей позиции, постоянно проверяя значение текущей позиции.
Позиция – аналогично местоположению пчелы на поле представляется координатами на плоскости x-y. Однако, в общем случае можно расширить эту идею в любое N-мерное пространство в соответствии с поставленной задачей. Это N-мерное пространство является областью решений для оптимизируемой задачи, где каждый набор координат представляет решение.
Пригодность — по аналогии с примером пчелиного роя функция пригодности будет плотностью цветов: чем больше плотность, тем лучше позиция. Функция пригодности служит средством связи между физической проблемой и алгоритмом оптимизации.
Персональная наилучшая позиция – по аналогии с пчелиным роем, каждая пчела помнит позицию, где она сама обнаружила наибольшее количество цветов. Эта позиция с наибольшим значением пригодности обнаруженная пчелой известна как персональная наилучшая позиция (ПНП). Каждая пчела имеет собственное ПНП, определяемое путем, который она пролетела. В каждой точке вдоль пути движения пчела сравнивает значение пригодности текущей позиции со значением ПНП. Если текущая позиция имеет значение пригодности выше, значение ПНП заменяется на значение текущей позиции.
Глобальная наилучшая позиция – каждая пчела также каким-то образом узнает область наибольшей концентрации цветов, определенную всем роем. Эта позиция наибольшей пригодности известна как глобальная наилучшая позиция (ГНП). Для всего роя это одна ГНП, к которой стремится каждая пчела. В каждой точке на протяжении всего пути каждая пчела сравнивает пригодность ее текущей позиции с ГНП. В случае если какая-либо пчела обнаружит позицию с более высокой пригодностью, ГНП заменяется текущей позицией этой пчелы.
Алгоритм метода роя пчел. Первым шагом в реализации МРП является выбор параметров, которые необходимо оптимизировать, и определение допустимого интервала для поиска оптимальных значений. Затем в допустимой области случайным образом располагаются пчёл, а также задаются векторы и скорости их движения. Затем каждая частица должна перемещаться через пространство решений, как если бы она была пчелой в рое. Алгоритм действует на каждую частицу отдельно, перемещая ее на небольшую величину, циклично двигая ее через весь рой. Следующие шаги выполняются для каждой частицы:
1. Оценка пригодности для частицы, сравнение с ПНП и ГНП. Функция пригодности, используя координаты частицы в пространстве решений, возвращает значение пригодности для текущей позиции. Если это значение больше, чем значение ПНП, соответствующее этой частице, или ГНП, тогда соответствующие позиции заменяются текущей позицией.
2. Корректировка скорости частицы. Манипуляции со скоростью частицы являются основным элементом всей оптимизации. Точное понимание уравнения, используемого для определения скорости, является ключом к пониманию всего процесса оптимизации. Скорость частицы меняется в соответствии с взаимным расположением позиций ПНП и ГНП. Она стремится в направлении этих позиций наибольшей пригодности в соответствии со следующим уравнением:
, где:
– это скорость частицы в n-том измерении на предыдущем шаге,
– это координата частицы в n-том измерении,
– ПНП,
– ГНП.
3. Расчет производится для каждого из N. Из этого уравнения видно, что новая скорость получается из старой скорости путем простого масштабирования на , и прибавления направления ГНП и ПНП для этого конкретного направления.
и
— это масштабные коэффициенты, которые определяют относительное взаимное «притяжение» к ПНП и ГНП. Они иногда рассматриваются как познавательный и социальный факторы.
— это коэффициент, определяющий какое влияние на частицу оказывает ее память о ПНП, и
— коэффициент, определяющий какое влияние на частицу оказывают остальные члены роя. Увеличение
предполагает исследование пространства решений путем движения каждой частицы в направлении своего ПНП; увеличение
предполагает исследование предполагаемого глобального максимума. Большинство реализаций используют две независимые случайные величины для стохастического изменения относительного притяжения ГНП и ПНП. Это введение случайного элемента в оптимизацию предназначено для моделирования незначительного непредсказуемого компонента реального поведения роя.
называют «инерционным весом» и это число (выбранное в интервале между 0 и 1) отражает в какой мере частица остается верной своему первоначальному курсу, не подвергшемуся влиянию ГНП и ПНП.
Метод роя пчёл можно эффективно распределить на несколько параллельных процессов, за счёт чего значительно увеличится его скорость.
Пчелиные алгоритмы подтверждают свою эффективность в качестве методов случайного поиска. К недостаткам данного метода стоит отнести большое число свободных параметров, от значения которых зачастую зависит результат, с другой стороны, отсутствуют основания для выбора этих значений.
Светлячковый алгоритм
Алгоритм светлячков предложен в 2007 г. Синь-Ши Янгом. Алгоритм использует следующую модель поведения светлячков:
· все светлячки могут привлекать друг друга, независимо от своего пола;
· привлекательность светлячка для других особей пропорциональна его яркости;
· менее привлекательные светлячки перемещаются в направлении более привлекательного светлячка;
· яркость излучения данного светлячка, видимая другим светлячком, уменьшается с увеличением расстояния между светлячками;
· если светлячок не видит возле себя светлячка более яркого, чем он сам, то он перемещается случайным образом.
Яркость излучения светлячка ,
, принимаем равной значению фитнесс-функции в его текущем положении.
Привлекательность светлячка для светлячка
полагаем равной
exp (
),
, i
j,
где расстояние между светлячками
и
;
взаимная привлекательность светлячков при нулевом расстоянии между ними;
вещественная величина, имеющая смысл коэффициента поглощения света среды.
Движение светлячка , который притягивается более привлекательным светлячком
, определяет формула
+
(
1;1),
, i
j,
где свободный параметр рандомизации. Для обеспечения приемлемого баланса между диверсификацией и интенсификацией поиска значение параметра рандомизации рекомендуют уменьшать с ростом нового поколения.
Схема алгоритма светлячков для задачи глобальной безусловной минимизации фитнесс-функции имеет следующий вид:
1. инициализируем начальную популяцию светлячков S = ( ) и вычисляем значения фитнесс-функции в начальных точках;
2. если , то по формуле вида (3) перемещаем светлячка
в направлении светлячка
, i
j;
3. вычисляем значения фитнесс-функции в полученных точках );
4. если условие окончания итераций не выполнено, то переходим к шагу 2.
В большинстве случаев можно использовать следующие значения свободных параметров алгоритма: =1;