Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Философия оптимизации и принятия решений

На главную Новости проекта Другие части Для отзывов

Часть 1. Что такое целевая функция. Проблема неполной оптимизации

Целевая функция - функция, которая показывает, как зависит оптимизируемый показатель от каких-то других параметров (например, прибыль фирмы от цен, спроса и т.д.). По сути это формализация понятия цели, с тем преимуществом, что теперь мы можем более-менее чётко оценить, насколько мы продвинулись на пути достижения цели или можем это сделать. Если параметры - аргументы целевой функции - нами управляемы, это особо удобно, но будем считать, что это не всегда так.

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

У системы может быть и не единственная цель. Что с этим делать, поговорим как-нибудь не сейчас, здесь предположим, что цель одна - надо начинать с вещей несложных.

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

Некоторые параметры, от которых зависит наше расстояние до цели, могут быть практически неуправляемыми нами. Яркий пример: средней силы футбольная команда хочет пройти групповой этап турнира. Жеребьевка от нее не зависит, могут попасться неудобные соперники. Стало быть, сила соперников - не зависящий от команды параметр.

Целевая функция - одно из важнейших исходных условий задач оптимизации. Если мы не определили такую функцию, то никакой оптимизации нет. Или есть, но не с нашей точки зрения. Ведь если у нас нет цели, мы же не можем сказать, что нам выгодно, а что нет.

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

Иногда мы знаем, что некоторая точка x0 - решение задачи классической оптимизации (далее для простоты будем полагать, что мы хотим, чтобы целевая функция приняла значение как можно больше). При этом мы не можем достичь этой точки. Как некоторые представительницы прекрасного пола хотят мужика, "чтоб не пил, не курил, и цветы всегда дарил, ... к футболу равнодушен, ..., тёщу мамой называл, ... и красив был, и умён". То есть как бы в известной песне нам указали, в какой точке целевая функция принимает оптимальное значение) Но вот только на практике такой идеал может и не попадаться (или выбрать другую). В результате бывает разумно что сделать? Согласиться на некоторые уступки, отказавшись от этой принце-оптимизации. Ну пусть, так и быть, кандидат иногда смотрит футбольные матчи, а на праздниках рюмочку коньячка примет. Да, значение функции уже не максимально, но близко к нему. На практике часто целесообразнее вести речь о такой вот неполной оптимизации.

Для ещё большего прояснения понятия вот такая картинка:

Как видим, теория не запрещает надеяться, что кто-нибудь когда-нибудь попадёт в точку (или даже попал, и мы его знаем и жутко хотели бы побить негодяя), но вот только мы туда попасть не можем. В итоге попадаем только в B, но можем продолжать мечтать о попадании в A, порой безо всякого смысла - ну мало ли чего можно хотеть?

Вспомните песню про Манхэттен. Сию несколько лет назад (где-то в 2008 году) во всю трещали по радиоприёмникам, пассажиры маршруток имели шанс и вовсе выучить её наизусть. Точка A: "Она хотела бы жить на Манхэттене и с Деми Мур делиться секретами". Точка B или нечто близкое к ней: "А он просто диджей на радио и он, в общем, не бедный парень...". Людей, не сумевших отказаться от сладких мечтаний, осознание неполной оптимизации может раздражать, но всё равно часто приходится мириться с тем, что в вершину A так и не попасть: "Так за годом год, за зимой зима..." - и живёт горе-поклонница манхэттенской романтики с этим диджеем.

Точка C - вообще актуальная штука, особенно у нас на Руси. Это когда человек живёт не очень-то, но на более высокие позиции не претендует, в принципе ситуация его устраивает. Точнее сказать, может, она и раздражает, но без мощного толчка вряд ли начнётся борьба за лучшее (по крайней мере точку B). А вот если и без того не чудесная ситуация ухудшается (скажем, до точки D), может начаться борьба - если не за B, то по крайней мере за C. Вспомните разные восстания из мировой истории. Ведь среди восстававших порой бывали как те, кто хотел радикально изменить ситуацию, так и те, кому надо было просто чтобы дали сносно жить.

Причины такой вот неполной оптимизации бывают разные. Ну вот парочка. 1) Только ограниченное число систем могут попасть в точку максимума или нечто совсем близкое (элитных мест на всех не хватит), уже попавшие установили монополию (или олигополию). 2) Монополизации нет, пытайтесь на здоровье, вот только нет и ресурсов. Ну можно же пытаться занять в спортивном турнире первое место, на это имеет право любой его участник, но вот только не у всех есть достаточный уровень. Кому-то вообще приходится ставить задачи типа "не оказаться в зоне вылета из лиги", "ну хотя бы пару этапов кубка пройти, даже в полуфинал вряд ли выйдем". Объединяет все эти причины вот что: мы знаем, что вообще-то можно жить и лучше, но не можем добиться воплощения мечтаний.

Может быть ситуация ещё лучше: а кто сказал, что мы вообще знаем точку максимума целевой функции? Может быть вот что. Мы подозреваем, что область допустимых значений параметров шире, чем известная нам, но вот только на практике мы пока что не смогли ни оправдать, ни опровергнуть своих подозрений. И вот обидно же, если точка классического оптимального значения как раз-таки в той области, которую мы не видим.

Яркий пример - хотел бы некий Вася одновременно порядочную, умную, суперски красивую девушку. Он знает, что теория не запрещает таким существовать, но на практике таких не видал. Время идёт, так он её и не видит. Область D1 включает в себя от девушек, которые по заданным критериям не очень до девушек, за которых не стыдно, но всё равно Васю они не впечатляют. Одна из таких девушек, которую Вася взял за неимением получше, по сути соответствует точке A на нашей картинке. Существование точки B подозревается, но не доказано (в отличие от ситуации, когда Вася такую девушку знает, но она его стопудово не примет). Это также нельзя считать оптимизацией в классическом понимании, когда нам надо именно наилучшее возможное решение: ведь мы не пришли к выводу, что A таковое.

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

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

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

Яркий современный пример использования дискретных систем для оптимизации непрерывных функций - программные алгоритмы оптимизации: комп в принципе дискретная штука, дискретны и переменные в языках программирования, хотя условно есть понятие "вещественный тип данных". Один из часто используемых методов оптимизации - перебор с заданным шагом:

Как видим, в точке A - настоящее оптимальное значение, B - "хороший" вариант, но на самом деле не лучший. Резумеется, чем меньше шаг, тем ближе мы к A.

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

copyright © Исканцев Н.В., 2012

На главную
X