Аннотация
Данный курсовой проект на тему «Оптимизация многомерной нелинейнойфункции. Слепой поиск». Необходимо было разработать программную модельчислового метода поиска экстремума функции двух переменных. Предусмотреть вводисходных данных и вывод с сохранением. Исследовать ограничения на вводимуюфункцию, обусловленные методом поиска и средствами моделирования.
Проект содержит 24 листа, включая приложение, листинг программы итаблицу – 1.
Введение
Прикладныенауки развиваются своим путем, используя существующий математический аппаратдля решения возникающих проблем, и даже своими потребностями стимулируют вразвитие некоторых разделов математики. Но в них нередко царят своятерминология, свои частные приемы решения задач, свои исходные предпосылки ицели. Имеют место ситуации, когда некорректно примененные прикладниками методы,тем не менее, позволяют получать полезные практические результаты. Дисциплина «Математическоемоделирование» давно сформировалась, как прикладная наука и включена вподготовку специалистов почти по всем экономическим техническим направлениям.
Математическоемоделирование как инструмент познания завоевывает все новые и новые позиции вразличных областях деятельности человека. Эта наука широко проникла в различныеобласти науки: экономические, социальные, биологические и многие другие, напервый взгляд, далекие от математики.
Основнаязадача моделирования различного рода процессов и систем с целью исследованияобъектов, прогнозирования их поведения или поиска наилучших условийфункционирования сводится к расчету анализируемых показателей по математическоймодели при тех или иных значениях (функциях) входных величин. Важное значениепри этом приобретают вычислительные алгоритмы, с помощью которых можно получитьпри моделировании решение конкретной математической задачи.
Знакомству сидеями и алгоритмами решения наиболее распространенных задач вычислительнойматематики, применяющихся при математическом моделировании, получениюпрактических навыков их применения.
Оно включаетв себя следующие основные темы.
· Интерполяция
· Аппроксимация
· Решениенелинейных уравнений и их систем
· Решениесистем линейных уравнений
· Вычислениеинтегралов
· Основырешения дифференциальных уравнений
· Методоптимизации.
1. Постановказадачи
1.1 Теоретическоеприложение
Концепцияметодов
В методахслучайного поиска величина шага /> припостроении улучшающей последовательности /> формируетсяслучайным образом. Поэтому в одной и той же ситуации шаг /> может быть различен вотличие от регулярных методов. «Методы случайного поиска являются прямымразвитием известного метода проб и ошибок, когда решение ищется случайно, и приудаче принимается, а при неудаче отвергается, с тем чтобы немедленно сноваобратиться к случайности как к источнику возможностей. Такое случайноеповедение разумно опирается на уверенность, что случайность содержит в себе всевозможности, в том числе и искомое решение во всех его вариантах».
В данномразделе рассматриваются следующие методы:
· Слепойпоиск
· Методслучайных направлений
· Методпоиска с «наказанием случайностью»
· Блуждающийпоиск
В целомслучайные методы поиска предпочтительнее регулярных в задачах высокойразмерности /> и вдали от оптимума.Поэтому здесь они рассматриваются преимущественно в ознакомительном плане. Методыэтой группы позволяют в среднем быстрее выходить в район оптимума. Эффективнырассматриваемые методы и при поиске глобального оптимума.
1.2Основные методы
1. Методслучайных направлений.
Из текущей(или заданной начальной) точки делается шаг в случайном направлении />, где /> – случайный вектор смодулем, равным единице (случайно только его направление); /> – коэффициентпропорциональности шага. Если /> />(при поиске минимумакритерия оптимальности), то новая точка принимается за текущую, и из нееделаются шаги в надежде найти лучшую точку. Если />,то делают новую попытку, то есть новый шаг />.
Поискзаканчивают, когда за заданное число попыток /> неудается найти точку с лучшим значением критерия оптимальности, чем имеющаясятекущая.
Существуютмодификации метода, в одной из которых после серии неудачных попыток /> уменьшается коэффициент />, что позволяет «уточнить»положение оптимума. В этом случае условием окончания является малость значенияшага (то есть />).
Существуеттакже модификация метода с обратным шагом. Отличительной ее особенностьюявляется то, что при неудачном шаге /> източки /> сразу производится шаг вобратном направлении />. При достаточномудалении от оптимума такая стратегия поиска может оказаться весьма эффективной.Если обратный шаг оказался неудачным, то можно сделать новый шаг из текущейточки или перейти к поиску с уменьшенным шагом. В последнем случае существуетопасность замедления поиска вдали от оптимума, особенно в овраге.
2. Методпоиска с «наказанием случайностью».
Метод является аналогом метода наискорейшего спуска, тольконаправление локального поиска не градиентное, а случайное. Как и в предыдущемметоде, из текущей точки делают случайные шаги до тех пор, пока не будетнайдена точка с лучшим значением критерия оптимальности. Затем в этомнаправлении регулярным методом одномерного поиска ищут оптимум. В точкеоптимума по направлению опять случайным образом ищут новое направление и т.д.
Условиемокончания обычно является невозможность получения лучшей точки из текущей запредварительно заданное число попыток />.
3. Методс «блуждающим поиском».
Данный метод являетсястатистическим расширением градиентного метода и реализуется в соответствии салгоритмом
/>
где /> – случайный вектор сединичным модулем, /> и /> – коэффициенты,характеризующие вклад случайной составляющей /> ирегулярной составляющей (/>) ввеличину шага.
Чаще в формуледля /> используется не градиент />, а составляющиенаправляющие косинусы градиента, что позволяет выдерживать заданное соотношениемежду регулярной и случайной составляющими шага.
Теоретическидоказывается, что данный алгоритм наиболее вероятно приведет к глобальномуэкстремуму. В алгоритме могут использоваться алгоритмы коррекции шага />, свойственные градиентномуметоду, который включается после /> неудачныхпопыток. Условием окончания является малость значения шага />.
Стратегияпоиска может предусматривать не постоянное, а периодическое добавлениеслучайного вектора к градиентному шагу. Частота случайных «скачков» должнауменьшаться по мере приближения к оптимуму и увеличиваться вдали от него. Дляэтого существуют специальные алгоритмы самообучения, например:
/>,
где /> – число шагов регулярнымградиентным методом без случайной составляющей, т.е. период добавленияслучайной составляющей;
/> –заданное целое число (рекомендуется />, приэтом в процессе поиска /> будет изменятьсяв диапазоне />).
Обратнопропорционально частоте «скачков» меняется и доля случайной составляющей вшаге, т.е. />. Условием окончания поискабудет, как и в регулярном градиентном методе, близость градиента к нулю.
МатематическоеописаниеМетод слепого поиска
Идея метода оченьпроста и наглядна. Случайным образом в допустимой области берется точка, исравнивается значение критерия в ней с текущим наилучшим. Если новая случайновзятая точка хуже хранящейся в качестве текущей лучшей, то берут другую точку.Если же нашли точку, в которой критерий лучше, то ее запоминают в качестветекущей лучшей. Гарантируется, что при неограниченном возрастании числа попытокмы будем приближаться к глобальному оптимуму, т.е. найденное текущее наилучшеезначение будет столь угодно близко к точному решению.
На практике поискпрекращают, когда число неуспешных попыток превышает наперед заданное число />.
Данный поиск можноприменять для поиска начального приближения, задав сравнительно небольшое числопопыток. Метод прост в алгоритмическом плане и не требует примера с конкретнымизначениями.
Для полученияслучайных чисел />, принадлежащихоткрытому интервалу (/>) используютфункцию преобразования
/>,
если нужны целыечисла, используют
/>.
2. Блок – схемаалгоритма моделирования/> /> /> /> /> /> /> /> /> />
/>Описание ввода – вывода
1 – вводим выбраннуюнами функцию;
2 – ввод выбранногонами интервала.
3 – вводим числоитераций;
4 – основной цикл длявычислений;
5 – реализацияслучайной величины для получения значений координат точки;
6 – вычисляемзначение функции;
7 – первая итерация;
8 – первоевычисляемое значение оптимально;
9 – выбираемследующее более оптимальное значение;
11 – текущее значениеявляется оптимальным;
12 – выводим X1, X2, Y оптимальные, т.е. выводимминимум функции
3. Инструментальныепрограммные средства
Программирование по Windows всегда было достаточносложной задачей. Интерфейс прикладного программирования (Application Programming Interface – API) Windows предоставляет враспоряжение набор мощных, но не всегда безопасных инструментов для разработкиприложений. С появлением Delphi ситуация изменилась. С помощью интерфейса для быстрой разработкиприложений (Rapid Application development – RAD) Delphi позволяет быстро и легко разработать приложение очень высокогоуровня. Используя Delphi, можно создавать и тестировать приложения со сложнымпользовательским интерфейсом без прямого использования функций API. Освобождаяпрограммиста от проблем, связанных с применением API, Delphi позволяетсконцентрироваться непосредственно на написании кода программы. Delphi – наиболее мнойизученная мощнейшая среда разработки, имеющая все необходимые функции дляразработки программной модели численного метода поиска экстремума функции.
4. Операционная средамоделирования
Windows XP – новая операционнаясистема фирмы Microsoft, непосредственно преемница Windows 2000. В основномповторяя архитектуру своей предшественницы, она делает свою работу накомпьютере более эффективно и предоставляет пользователю много дополнительныхвозможностей, кроме того появился новый интерфейс
Основные задачи,связанные с работой в среде Windows 98:
· ЗагрузкаWindows XP и завершение работы на компьютере
· Получениепомощи по ходу работы
· Выбортипа пользовательского интерфейса
· Использованиестандартных панелей
· Сменаязыка
· Управлениезагрузкой Windows XP
Обладая вытесняющеймногозадачностью, способностью исполнять несколько программ одновременно иперераспределять ресурсы компьютера между ними по собственной инициативе.
Имеет высокий уровеньсовместимости с ранее накопленном программным обеспечением, котороеразрабатывалось для MS-DOS и предыдущих версий Windows
Требования Windows XP к компьютеру:
· Микропроцессорработающий с тактовой частотой 400МГц (Pentium, Pentium Pro, Pentium 3,4)
· МышьюMicrosoft Mouse или другими, подобными по функциям устройствам
· Оперативнаяпамять не менее 64 Мбайт
5. Контрольная задача
Пример:
1. Требуется найтиминимум функции
/>, где />
2. Интервал поиска
/>/>
3. Начальная точка: />
4. Параметры поиска:коэффициент шага /> число попыток вкаждой точке />
Результаты вычисленийпредставлены в таблице 1.
Номер итерации
Х/>
Х/> F Попытка 1 -0.4282 -0.8868 7.3722
УДАЧНО 2 -0.3375 -0.9057 7.3722 Неудачно 3 -0.3375 -0.7358 7.3722 Неудачно 4 -0.2469 -0.7358 7.3722 Неудачно 5 -0.2166 -0.5660 7.3722 Неудачно 6 -0.1965 -0.3962 7.3722 Неудачно 7 -0.1159 -0.3019 7.3722 Неудачно 8 -0.1864 -0.1887 1.7359
УДАЧНО 9 -0.2771 -0.1132 1.7359 Неудачно 10 -0.1864 -0.1509 1.2884
УДАЧНО 11 -0.0957 -0.1887 1.2884 Неудачно 12 -0.0353 -0.0566 1.2884 Неудачно 13 -0.0856 0.0943 1.2884 Неудачно 14 -0.0151 0.2075 1.2884 Неудачно 15 0.8514 0.9623 -3.8412 УДАЧНО 16 0.9421 0.9057 -3.8412 Неудачно 17 0.9824 1.0755 -3.9723
УДАЧНО
Последнюю точку (17)можно считать решением, так как за заданное число попыток (17), не удалосьнайти лучшую точку. Возможно увеличив число таких попыток, можно найти лучшеерешение. Вывод можно сделать такой: данная программа удачно справляется с возложеннымина неё задачами
/>
Заключение
Данная программаможет быть использована в качестве наглядного пособия для изучения оптимизациимногомерной нелинейной функции методом слепого поиска. Обеспечивает корректнуюработу и вывод результатов.
Программа также можетприменяться для оптимального проектирования (выбор наилучших технологических режимов,структуры технологических цепочек, условий экономической деятельности),оптимального управления, построение нелинейных математических модулей, объектовуправления (минимизации различных структуры модели и реального объекта).
Недостатком даннойпрограммы является отсутствие графического представления моделирования, однакодля его осуществления, необходимо ограничивать диапазона выбираемого дляподсчёта интервала, что напрямую сказывается на полезность программы.
Список используемойлитературы
1. Ю.В. Васильков, Н.Н. Василькова«Компьютерные технологии вычислений в математическом моделировании»
2. Род Стивенс «Delphi. Готовые алгоритмы»,М., 2004
3. А.Я. Архангельский «Delphi 7. Справочноепособие», М., 2004
4. А.Я. Архангельский«Программирование в Delphi 7», М., 2004
Приложение
Листинг программы
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,StdCtrls, Spin, Grids, Buttons, Menus;
type
TForm1 =class(TForm)
GroupBox1:TGroupBox;
Label1:TLabel;
Label2:TLabel;
Label3:TLabel;
Label4:TLabel;
Label5:TLabel;
Label6:TLabel;
ComboBox1:TComboBox;
Label7:TLabel;
Label8:TLabel;
Label9:TLabel;
ComboBox2:TComboBox;
Label10:TLabel;
Label11:TLabel;
ComboBox3:TComboBox;
Label12:TLabel;
Label13:TLabel;
GroupBox2:TGroupBox;
Label14:TLabel;
Label15:TLabel;
Label16:TLabel;
Label17:TLabel;
Label18:TLabel;
Label19:TLabel;
Label20:TLabel;
Label21:TLabel;
GroupBox3:TGroupBox;
SpinEdit9:TSpinEdit;
StringGrid1:TStringGrid;
GroupBox4:TGroupBox;
Label22:TLabel;
Label23:TLabel;
Label24:TLabel;
Label25:TLabel;
GroupBox5:TGroupBox;
SpinEdit10:TSpinEdit;
Edit1:TEdit;
Edit2:TEdit;
Edit3:TEdit;
Edit4:TEdit;
Edit5:TEdit;
Edit6:TEdit;
Edit7:TEdit;
Edit8:TEdit;
Edit9:TEdit;
Edit10:TEdit;
Edit11:TEdit;
MainMenu1:TMainMenu;
File1:TMenuItem;
Close1:TMenuItem;
N1:TMenuItem;
Label26:TLabel;
GroupBox6:TGroupBox;
SpeedButton1:TSpeedButton;
procedureFormCreate (Sender: TObject);
procedureSpeedButton1Click (Sender: TObject);
procedureClose1Click (Sender: TObject);
procedureN1Click (Sender: TObject);
private
{Privatedeclarations}
public
{Publicdeclarations}
end;
var
Form1:TForm1;
implementation
uses Math,Unit2;
{$R *.dfm}
procedureTForm1. FormCreate (Sender: TObject);
begin
// задаём названиязаголовков грайда
StringGrid1. Cols[0].Text:='№итер.';
StringGrid1.Cols[1].Text:='X1';
StringGrid1.Cols[2].Text:='X2';
StringGrid1.Cols[3].Text:='Значение функции';
StringGrid1.Cols[4].Text:='Попытка';
end;
procedureTForm1. SpeedButton1Click (Sender: TObject);
var I: Integer;
A, B, C,D, x11, x12, x21, x22, x1, x2, x1opt, x2opt, y, Yopt:real;
begin
// присваиваемдля удобства значения переменных
A:=StrToFloat(Edit1. Text);
B:=StrToFloat(Edit2. Text);
C:=StrToFloat(Edit3. Text);
D:=StrToFloat(Edit4. Text);
x11:=StrToFloat(Edit5. Text);
x12:=StrToFloat(Edit6. Text);
x21:=StrToFloat(Edit7. Text);
x22:=StrToFloat(Edit8. Text);
// создаем в грайдестроки
StringGrid1. RowCount:=SpinEdit9.Value+1;
for I:=1to SpinEdit9. Value do
BEGIN
// получениеслучайных значений координат точки
{**************************************}
randomize;
x1:= (x12 –x11) *random+ x11;
x2:= (x22 –x21) *random+ x21;
{**************************************}
// вычисляем значениефункции
if (ComboBox1. Text='-')and (ComboBox2. Text='-') and (ComboBox3. Text='-')
then
y:=A*(x1*x1*x1)– B*(x2*x2) – C*x1 – D*x2;
if(ComboBox1. Text='-') and (ComboBox2. Text='-') and (ComboBox3. Text='+')
then
y:=A*(x1*x1*x1)– B*(x2*x2) – C*x1 + D*x2;
if(ComboBox1. Text='-') and (ComboBox2. Text='+') and (ComboBox3. Text='-')
then
y:=A*(x1*x1*x1)– B*(x2*x2) + C*x1 – D*x2;
if(ComboBox1. Text='+') and (ComboBox2. Text='-') and (ComboBox3. Text='-')
then
y:=A*(x1*x1*x1)+ B*(x2*x2) – C*x1 – D*x2;
if(ComboBox1. Text='+') and (ComboBox2. Text='+') and (ComboBox3. Text='-')
then
y:=A*(x1*x1*x1)+ B*(x2*x2) + C*x1 – D*x2;
if(ComboBox1. Text='-') and (ComboBox2. Text='+') and (ComboBox3. Text='+')
then
y:=A*(x1*x1*x1)– B*(x2*x2) + C*x1 + D*x2;
if(ComboBox1. Text='+') and (ComboBox2. Text='+') and (ComboBox3. Text='+')
then
y:=A*(x1*x1*x1)+ B*(x2*x2) + C*x1 + D*x2;
if(ComboBox1. Text='+') and (ComboBox2. Text='-') and (ComboBox3. Text='+')
then
y:=A*(x1*x1*x1)+ B*(x2*x2) – C*x1 + D*x2;
// проверка номераитерации
if i=1 then
begin
x1opt:=x1;
x2opt:=x2;
Yopt:=y;
end
else
begin
ifYopt>y then
// выбираем следуещееболее оптимальное значение
begin
x1opt:=x1;
x2opt:=x2;
Yopt:=y;
StringGrid1.Cells [4, i]:='УДАЧНАЯ';
end
elseStringGrid1. Cells [4, i]:='неудачная';
end;
// добавляем данные вграйд
StringGrid1.Cells [0, i]:=inttostr(i);
StringGrid1.Cells [1, i]:=FloatToStrF (x1, ffFixed, 15, SpinEdit10. Value);
StringGrid1.Cells [2, i]:=FloatToStrF (x2, ffFixed, 15, SpinEdit10. Value);
StringGrid1.Cells [3, i]:=FloatToStrF (y, ffFixed, 15, SpinEdit10. Value);
END;
Edit9. Text:=FloatToStrF(x1opt, ffFixed, 15, SpinEdit10. Value);
Edit10. Text:=FloatToStrF(x2opt, ffFixed, 15, SpinEdit10. Value);
Edit11. Text:=FloatToStrF(Yopt, ffFixed, 15, SpinEdit10. Value);
end;
procedureTForm1. Close1Click (Sender: TObject);
begin
close;
end;
procedureTForm1.N1Click (Sender: TObject);
begin
Beep;
// показываеммодально какое-нибудь окно о проге
form2. ShowModal;
end;
end.