Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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



Введение

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

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

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

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



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

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

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

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

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

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

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

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

BitTableProblem.java

package main;

import ec. EvolutionState;

import ec. Individual;

import ec.gp.GPIndividual;

import ec.gp.GPProblem;

import ec.gp.koza. KozaFitness;

import ec.simple. SimpleProblemForm;

import java.io. FileInputStream;

import java.io. FileNotFoundException;

import java.util. Scanner;

public class DoubleTableProblem extends GPProblem implements SimpleProblemForm {

int n, m;

double[][] matr;

private double [] arr = new double[5];

public double get (int pos) {

if (pos >n) {

return 0.0d;

}

return arr [pos-1];

}

public void readfile() throws FileNotFoundException {

Scanner sc= new Scanner (new FileInputStream («input.txt»));

n=sc.nextInt();

m=sc.nextInt();

matr=new double [m] [n+1];

for (int i=0; i<m; i++)

for (int j=0; j<=n; j++)

try {

matr[i] [j]=sc.nextDouble();

} catch (RuntimeException re) {

System.out.println («» + i +» " + j);

throw re;

}

}

@Override

public void evaluate (EvolutionState es, Individual indvdl, int subpop, int threadnum) {

if (indvdl.evaluated) {

return;

}

int hits = 0;

DoubleData data = (DoubleData) input;

try {

readfile();

} catch (FileNotFoundException ex) {

throw new RuntimeException(ex);

}

double pogr=0;

for (int i =0; i<matr.length; i++) {

parse(i);

double estimated = matr[i] [n];

((GPIndividual) indvdl).trees[0].child.eval (es, threadnum, data, stack, (GPIndividual) indvdl, this);

double delta = Math.abs (estimated-data.value);

pogr += delta;

if (delta <= 0.001) {

hits++;

}

}



KozaFitness fitness = (KozaFitness) indvdl.fitness;

fitness.setStandardizedFitness (es, pogr);

indvdl.evaluated = true;

fitness.hits = hits;

}

private void parse (int value) {

for (int i=0; i<=n; i++)

arr[i]=matr[value] [i];

}

}

DoubleData.java

package main;

import ec.gp.GPData;

public class DoubleData extends GPData {

public double value;

@Override

public void copyTo (GPData data) {

((DoubleData) data).value = value;

}

}

Chact.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class Chast extends GPNode {

@Override

public String toString() {

return «/»;

}

@Override

public int expectedChildren() {

return 2;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

children[1].eval (es, i, input, adfs, gpi, prblm);

result/=data.value;

data.value = result;

}

}

Sin.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class Sin extends GPNode {

@Override

public String toString() {

return «sin»;

}

@Override

public int expectedChildren() {

return 1;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

data.value =Math.sin(result);

}

}

Cos.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class Cos extends GPNode {

@Override

public String toString() {

return «cos»;

}

@Override

public int expectedChildren() {

return 1;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

data.value =Math.cos(result);

}

}

Proiz.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class Proiz extends GPNode {

@Override

public String toString() {

return «*»;

}

@Override

public int expectedChildren() {

return 2;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

children[1].eval (es, i, input, adfs, gpi, prblm);

result*=data.value;

data.value = result;

}

}

Raz.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class Raz extends GPNode {

@Override

public String toString() {

return «-»;

}



@Override

public int expectedChildren() {

return 2;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

children[1].eval (es, i, input, adfs, gpi, prblm);

result-=data.value;

data.value = result;

}

}

Summ.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;



public class Summ extends GPNode {

@Override

public String toString() {

return «+»;

}

@Override

public int expectedChildren() {

return 2;

}

@Override

public void eval (EvolutionState es, int i, GPData input, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) input;

children[0].eval (es, i, input, adfs, gpi, prblm);

double result = data.value;

children[1].eval (es, i, input, adfs, gpi, prblm);

result+=data.value;

data.value = result;

}

}

X.java

package main;

import ec. EvolutionState;

import ec. Problem;

import ec.gp.ADFStack;

import ec.gp.GPData;

import ec.gp.GPIndividual;

import ec.gp.GPNode;

public class X extends GPNode {

@Override

public String toString() {

return «x»;

}

@Override

public int expectedChildren() {return 0;}

@Override

public void eval (EvolutionState es, int i, GPData gpdata, ADFStack adfs, GPIndividual gpi, Problem prblm) {

DoubleData data = (DoubleData) gpdata;

DoubleTableProblem table = (DoubleTableProblem) prblm;

data.value = table.get(1);

}

}

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

package main;

import java.io. File;

import java.io.IOException;

import java.io. PrintWriter;

public class MyFunction {

double F (double x) {

double otv;

if (x==1) {

otv = 0;

} else {

otv = Math.sin(x)+(Math.pow (x, 2)/(1-x));

}

return otv;

}

public void printToFile (int n) throws IOException {

double matrFx[][] = new double[n] [2];

File file = new File («input.txt»);

if (! file.exists()) {

file.createNewFile();

}

try (PrintWriter out = new PrintWriter (file.getAbsoluteFile())) {

out.println («1 «+n);

out.println («0 0,0»);

double sum1 = 0;

double sum2 = 0;

for (int i=1; i<n; i++) {

if (i % 2==0) {

sum2 += F (matrFx[i] [1]);

}

if (i % 2==1) {

sum1 += F (matrFx[i] [1]);

}

matrFx[i] [1]=(0.33333333333334)*(F(0)+F(n)+2*sum2+4*sum1);

String itfx = «»;

String in = String.valueOf (matrFx[i] [1]);

char[] ins = in.toCharArray();

for (int j=0; j<ins.length; j++) {

if (ins[j] == '.') {

ins[j]=', ';

}

itfx += ins[j];

}

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

}

}

}

/**

* @param args the command line arguments

* @throws java.io.IOException

*/

public static void main (String[] args) throws IOException {

System.out.println («Генерируем файл»);

MyFunction1 abc = new MyFunction1 ();

abc.printToFile(100);

}

}



Заключение

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



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

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

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

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

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

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

Размещено на Allbest.ru