Исследование алгоритма оптимизации
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
?одились исследование метода
Пусть нам дана функция
Проведём вычисления и сравним их с нулём
2
3
Таблица 2:Результаты для тестовых фунций
Интенсификация поиска. Чтобы углубить поиск в перспективных областях, мы должны возвратиться к одному из уже найденных лучшему решению. Тогда размер списка запретов может быть просто сокращен для малого числа итераций. В некоторых случаях могут быть использованы более сложные методики. Некоторые проблемы оптимизации могут быть разделены на подпроблемы.
Решение этих подпроблем оптимально и объединение частных решений приводит к оптимальному решению. Трудность такой стратегии, очевидно, состоит в нахождении хорошего разделения. Как упомянуто ранее, для основы, связанной с вычислительным временем, быстрые эвристики и окрестность рационального размера используется на каждом шаге TS. Методы по углублению поиска используют или более продуманные эвристики или методы строгого сглаживания или расширенную окрестность. Также возможно выполнить интенсификацию, основанную на долгосрочной памяти. Каждое решение или перемещение может быть характеризовано набором компонентов. Компоненты хороших перемещений или хороших решений запоминаются. В течении фазы интенсификации решения и перемещения оцениваются принятым во внимание количеством хороших компонентов. Эта долгосрочная память может быть рассмотрена, как своего рода процесс обучения.
3. Экспериментальное исследование средней трудоемкости алгоритма
Экспериментальное исследование средней трудоемкости алгоритма будет производиться путем подсчета количества циклов, затрачиваемых процессором на прогон алгоритма на заданном наборе параметров.
Подготовка данных модели для эксперимента сводится к формированию XML файла с параметрами модели, при этом используется приложение Experiment Designer. Для принятых значений точности представления параметров функции качества проводится исследование алгоритма. Для проведения эксперимента используется модель ModelGAProfiled.exe.
Проведение замера количества циклов, выполняемых процессором, для прогона модели, будет производиться с использованием программного обеспечения Performance Analysis, входящего в состав Compuware DevParthner Studio. Для статистической значимости результатов, проводится 10 параллельных опытов. Т.е. при тех же параметрах модели производится повторный запуск программы 10 раз. Получаемые значения kij заносятся в таблицу. Для статистического анализа будет использоваться ПО STATISTICA 6.0.
После проведения всех экспериментов для полученных значений вычисляется среднее и квадратичное отклонение, которые заносятся в ту же таблицу: Mean, SD.
Аналогично проводятся эксперименты для всех функций качества.
Полученные данные представлены в Приложении А.
Для исключения времени, затрачиваемого на вычисления функции качества, выносится значение qij. Полученные данные представлены в Приложении Б.
По результатам экспериментов строятся графики экспериментальной оценки трудоемкости алгоритма. Данные находятся в приложении В.
Все эксперименты производились на компьютере со следующей конфигурацией: Intel(R) Pentium(R)4 (2,4 Ггц), 512 Mb DDR SDRAM, Windows XP Professional Service Pack 2.
Приложение А
Текст программы:
#include
#include
#include
#include
#include
#include
#include "randfunc.h"
/* Дайте название файлу */
#include "probl01.h"
#define TRUSSPROBL 1
/* Дайте соответствующее два параметра. */
/* Выберите размер */
#define TAMPOBL 20
#define TOP 2
#define SEMIFACTIBLE 1
#define FACTIBLE 2
#define DESCONOCIDA 3
#define NO_FACTIBLE 4
/*Введите соответсвующие функции. */violacionInic(float *);violacion(struct individuo *, float *);creenciasInic(struct creencias *);poblacionInic(struct individuo *, struct creencias *);actualizaCreencias(struct individuo *, struct creencias *, int);expande(struct celda *, struct individuo *, struct creencias *);aceptar(struct individuo *);compAptitud(const void *, const void *);generarHijos(struct individuo *, struct creencias *);mueve(int, int, float, struct individuo *, struct creencias *);celda *cercana(int, struct celda *);celda *busca(int, struct celda *);selecciona(struct individuo *);compVictorias(const void *, const void *);nuevoInd(struct individuo *);extremos(int *, int *, struct individuo *);media;
/* объявите структуру*/*tzstr = "TZ=PST8PDT";timeb tiempo1, tiempo2;diferencia;(int argc, char **argv) {i, j, indmin, indmax, Gmax;semilla;gmax[NUMCONSTR];cadena[25];evs = 0;*a;creencias espcreencias;individuo pobl[2*TAMPOBL + 3];(argc == 4) {= atoi(argv[1]);= atof(argv[2]);(cadena, argv[3]);
}{("Teclee el nъmero mбximo de generaciones: ");("%d", &Gmax);("Teclee la semilla de aleatorios (0..1): ");("%f", &semilla);("Teclee el nombre del archivo de salida: ");("%s", cadena);
}( (a = fopen(cadena, "w")) == NULL ) {("Error al abrir el archivo de salida.\n");(1);
}(a, "Nъmero mбximo de generaciones: %d\n", Gmax);(a, "Semilla de aleatorios %f\n\n", semilla);(tzstr);();= 0;(semilla);();(gmax);(&espcreencias);(pobl, &espcreencias);(i = 0; i < TAMPOBL; i++) {(&(pobl[i]), 0, 0, 0);(&(pobl[i]), gmax);++;
}(j = 0; j < Gmax; j++) {(pobl, &espcreencias, j);(pobl, &espcreencias);(i = TAMPOBL; i < 2*TAMPOBL; i++) {(&(pobl[i]), 0, 0, 0);(&(pobl[i]), gmax);++;
}(pobl);(j >= Gmax - 11 || (j+1)%(Gmax/100) == 0) {(&indmin, &indmax, pobl);(a, "Generaciуn %d\n", j+1);(a, "Aptitud media: %0.7f, aptitud mбxima: %0.7f, aptitud mнnima: %0.7f\n", media, pobl[indmax].aptitud, pobl[indmin].aptitud);(a, "Mejor individuo:");(i = 0; i < VARIABLES; i++) {(a, " %0.7f,", pobl[indmin].variable[i]);
}(i = 0; i < NUMCONSTR; i++) {(a, "\ng%d = %0.7f", i+1, pobl[indmin].g[i]);
}(a, "\nviol = %0.7f", pobl[indmin].viol);(a, "\nEl mejor individuo es ");(!pobl[indmin].factible) {(a, "no ");
}(a, "factible.\nEvluaciones: %ld\n\n", evs);
}
}(a);("%0.7f", pobl[indmin].aptitud);(!pobl[indmin].factible) {(" i");
}("\n");(0);
}creenciasInic(struct creencias *esp) {i;l[VARIABLES], u[VARIABLES];(l, u);(i = 0; i up[i] = u[i];
}>raiz = (struct celda *) malloc(sizeof(struct celda));>raiz->padre = NULL;>raiz->hijo = NULL;>raiz->profundidad = PROFUNDIDAD_MAX;
}poblacionInic(struct individuo *pobl