Генетическое программирование

Курсовая работа

Генетическое программирование

Введение

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

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

Автоматное программирование - парадигма программирования, при использовании которой программу предлагается строить в виде совокупности поставщиков событий, объектов управления и системы управляющих взаимодействующих конечных автоматов. Поставщик событий характеризуется множеством событий, которые он может генерировать. Объект управления характеризуется множеством вычислительных состояний, а также двумя наборами функций: множеством предикатов, отображающих вычислительное состояние в логическое значение (истина или ложь), и множеством действий, позволяющих изменять вычислительное состояние. Управляющий автомат определяется конечным множеством управляющих состояний, функцией переходов и функцией действий.

Управляющие конечные автоматы часто характеризуются сложным поведением, как например, в задачах об «Умном муравье» и «Летающие тарелки», рассматриваемых в настоящей работе. В таком случае их проектирование представляет собой весьма трудоемкую задачу. Эта задача становится еще более сложной в случае проектирования системы взаимодействующих автоматов или в случае наличия в системе нескольких взаимодействующих агентов, каждый из которых управляется отдельным автоматом. Возникает естественное желание - автоматизировать процесс проектирования автоматов, поручив основную работу компьютеру.

1. Анализ технического задания

Необходимо построить приложение, позволяющее находить интеграл для функции y = (x).

Данное приложение в качестве входных данных должно обрабатывать следующего формата, первая строка файла содержит целое число N (1N≤100).

Следующие N строк содержат пары вещественных чисел вида: x_i, y_i.

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

{+,-,*,/, sin, cos}

2. Описание промежуточных узлов

алгоритм приложение интеллект интеграл

BitTableProblem.java

package main;ec. EvolutionState;ec. Individual;ec.gp.GPIndividual;ec.gp.GPProblem;ec.gp.koza. KozaFitness;ec.simple. SimpleProblemForm;java.io. FileInputStream;java.io. FileNotFoundException;java.util. Scanner;class DoubleTableProblem extends GPProblem implements SimpleProblemForm {

n, m;[][] matr;double [] arr = new double[5];

double get (int pos) {(pos >n) {0.0d;

}arr [pos-1];

}void readfile() throws FileNotFoundException {sc= new Scanner (new FileInputStream («input.txt»));

=sc.nextInt();=sc.nextInt();

=new double [m] [n+1];(int i=0; i<m; i++)(int j=0; j<=n; j++){[i] [j]=sc.nextDouble();

} catch (RuntimeException re) {.out.println («» + i +» " + j);re;

}

}

@Overridevoid evaluate (EvolutionState es, Individual indvdl, int subpop, int threadnum) {(indvdl.evaluated) {;

}hits = 0;data = (DoubleData) input;

{();

} catch (FileNotFoundException ex) {new RuntimeException(ex);

}

pogr=0;

(int i =0; i<matr.length; i++) {(i);estimated = matr[i] [n];

((GPIndividual) indvdl).trees[0].child.eval (es, threadnum, data, stack, (GPIndividual) indvdl, this);delta = Math.abs (estimated-data.value);+= delta;(delta <= 0.001) {++;

}

}

KozaFitness fitness = (KozaFitness) indvdl.fitness;.setStandardizedFitness (es, pogr);.evaluated = true;.hits = hits;

}void parse (int value) {(int i=0; i<=n; i++)[i]=matr[value] [i];

}

}

DoubleData.java

package main;

ec.gp.GPData;

class DoubleData extends GPData {double value;

@Overridevoid copyTo (GPData data) {

((DoubleData) data).value = value;

}

}

Chact.java

package main;ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class Chast extends GPNode {

@OverrideString toString() {«/»;

}

@Overrideint expectedChildren() {2;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);

result = data.value;

[1].eval (es, i, input, adfs, gpi, prblm);/=data.value;.value = result;

}

}

Sin.java

package main;

ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class Sin extends GPNode {

@OverrideString toString() {«sin»;

}

@Overrideint expectedChildren() {1;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);result = data.value;.value =Math.sin(result);

}

}

Cos.java

package main;

ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class Cos extends GPNode {

}

@Overrideint expectedChildren() {1;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);

result = data.value;.value =Math.cos(result);

}

}

Proiz.java

main;

ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class Proiz extends GPNode {

@OverrideString toString() {«*»;

}

@Overrideint expectedChildren() {2;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);result = data.value;

[1].eval (es, i, input, adfs, gpi, prblm);*=data.value;.value = result;

}

}

Raz.java

package main;

ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class Raz extends GPNode {

@OverrideString toString() {«-»;

}

@Overrideint expectedChildren() {2;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);result = data.value;[1].eval (es, i, input, adfs, gpi, prblm);=data.value;.value = result;

}

}

Summ.java

package main;

ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

public class Summ extends GPNode {

@OverrideString toString() {«+»;

}

@Overrideint expectedChildren() {2;

}

@Overridevoid eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) input;[0].eval (es, i, input, adfs, gpi, prblm);result = data.value;

[1].eval (es, i, input, adfs, gpi, prblm);+=data.value;.value = result;

}

}

X.java

package main;ec. EvolutionState;ec. Problem;ec.gp.ADFStack;ec.gp.GPData;ec.gp.GPIndividual;ec.gp.GPNode;

class X extends GPNode {

@OverrideString toString() {«x»;

}

@Overrideint expectedChildren() {return 0;}

@Overridevoid eval (EvolutionState es, int i, GPData gpdata, ADFStack adfs, GPIndividual gpi, Problem prblm) {data = (DoubleData) gpdata;table = (DoubleTableProblem) prblm;.value = table.get(1);

}

}

Класс, генератор файла с парами значений (Myfunction.java)

package main;

java.io. File;java.io.IOException;java.io. PrintWriter;class MyFunction {F (double x) {otv;(x==1) {= 0;

} else {= Math.sin(x)+(Math.pow (x, 2)/(1-x));

}otv;

}

void printToFile (int n) throws IOException {matrFx[][] = new double[n] [2];file = new File («input.txt»);

(! file.exists()) {.createNewFile();

}

(PrintWriter out = new PrintWriter (file.getAbsoluteFile())) {.println («1 «+n);.println («0 0,0»);sum1 = 0;sum2 = 0;(int i=1; i<n; i++) {(i % 2==0) {+= F (matrFx[i] [1]);

}(i % 2==1) {+= F (matrFx[i] [1]);

}[i] [1]=(0.33333333333334)*(F(0)+F(n)+2*sum2+4*sum1);itfx = «»;in = String.valueOf (matrFx[i] [1]);[] ins = in.toCharArray();

(int j=0; j<ins.length; j++) {(ins[j] == '.') {[j]=', ';

}+= ins[j];

}.println (i+» «+itfx);

}

}

}

/**

* @throws java.io.IOException

*/static void main (String[] args) throws IOException {.out.println («Генерируем файл»);abc = new MyFunction1 ();.printToFile(100);

}

}

Заключение

В ходе выполнения работы был реализован пример генетического программирования согласно индивидуальному варианту

Список использованных источников

1.   Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. - М.: Наука, УДК 519.6, - 223 c., 1979, 406 с.

2.      Колесников А.А. Аналитическое конструирование нелинейных оптимальных систем. Таганрог: Изд-во ТРТУ, 1984, 72 с.

.        Рафиков Г.Ш. Цифровые системы управления. Конспект лекций. - Донецк, 1999, 102 с.

4.      Tsinias J. Sufficient Lyapunov-like conditions for stabilization Mat. Contr. Signals Syst. 1989. Vol. 2. #12. Pр 343 - 357.

.        Егоров А.И. Оптимальное управление тепловыми и диффузионными процессами. М.: Наука, 1978, 468 с.