ga算法java代码 java算法编程

java编程，题目要求如下。

class Base

公司专注于为企业提供成都网站设计、成都网站制作、微信公众号开发、电子商务商城网站建设，微信小程序开发，软件按需开发网站等一站式互联网企业服务。凭借多年丰富的经验，我们会仔细了解各客户的需求而做出多方面的分析、设计、整合，为客户设计出具风格及创意性的商业解决方案，创新互联更提供一系列网站制作和网站推广的服务。

{

protected String name;

protected getScore(){return 0;};

}

class Team extends Base

{

private int gf;

private int ga;

private int pts;

private int gd;

public Team(int Gf,int Ga)

{

gf=Gf;

ga=Ga;

gd=gf-ga;

if(gd0)

{

pts=3

}

else if(gd==0)

{

pts=1;

}

else

{

pts=0;

}

}

public int getScore()

{

return pts*10 + gd*5 + gf;

}

}

//大概是这样了,看在我大晚上给你写代码的份上，给我分吧

如何用Java实现遗传算法？

通过遗传算法走迷宫。虽然图1和图2均成功走出迷宫，但是图1比图2的路径长的多，且复杂，遗传算法可以计算出有多少种可能性，并选择其中最简洁的作为运算结果。

示例图1：

示例图2：

实现代码：

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Random;

/**

* 用遗传算法走迷宫

*

* @author Orisun

*

*/

public class GA {

int gene_len; // 基因长度

int chrom_len; // 染色体长度

int population; // 种群大小

double cross_ratio; // 交叉率

double muta_ratio; // 变异率

int iter_limit; // 最多进化的代数

Listboolean[] individuals; // 存储当代种群的染色体

Labyrinth labyrinth;

int width;      //迷宫一行有多少个格子

int height;     //迷宫有多少行

public class BI {

double fitness;

boolean[] indv;

public BI(double f, boolean[] ind) {

fitness = f;

indv = ind;

}

public double getFitness() {

return fitness;

}

public boolean[] getIndv() {

return indv;

}

}

ListBI best_individual; // 存储每一代中最优秀的个体

public GA(Labyrinth labyrinth) {

this.labyrinth=labyrinth;

this.width = labyrinth.map[0].length;

this.height = labyrinth.map.length;

chrom_len = 4 * (width+height);

gene_len = 2;

population = 20;

cross_ratio = 0.83;

muta_ratio = 0.002;

iter_limit = 300;

individuals = new ArrayListboolean[](population);

best_individual = new ArrayListBI(iter_limit);

}

public int getWidth() {

return width;

}

public void setWidth(int width) {

this.width = width;

}

public double getCross_ratio() {

return cross_ratio;

}

public ListBI getBest_individual() {

return best_individual;

}

public Labyrinth getLabyrinth() {

return labyrinth;

}

public void setLabyrinth(Labyrinth labyrinth) {

this.labyrinth = labyrinth;

}

public void setChrom_len(int chrom_len) {

this.chrom_len = chrom_len;

}

public void setPopulation(int population) {

this.population = population;

}

public void setCross_ratio(double cross_ratio) {

this.cross_ratio = cross_ratio;

}

public void setMuta_ratio(double muta_ratio) {

this.muta_ratio = muta_ratio;

}

public void setIter_limit(int iter_limit) {

this.iter_limit = iter_limit;

}

// 初始化种群

public void initPopulation() {

Random r = new Random(System.currentTimeMillis());

for (int i = 0; i population; i++) {

int len = gene_len * chrom_len;

boolean[] ind = new boolean[len];

for (int j = 0; j len; j++)

ind[j] = r.nextBoolean();

individuals.add(ind);

}

}

// 交叉

public void cross(boolean[] arr1, boolean[] arr2) {

Random r = new Random(System.currentTimeMillis());

int length = arr1.length;

int slice = 0;

do {

slice = r.nextInt(length);

} while (slice == 0);

if (slice length / 2) {

for (int i = 0; i slice; i++) {

boolean tmp = arr1[i];

arr1[i] = arr2[i];

arr2[i] = tmp;

}

} else {

for (int i = slice; i length; i++) {

boolean tmp = arr1[i];

arr1[i] = arr2[i];

arr2[i] = tmp;

}

}

}

// 变异

public void mutation(boolean[] individual) {

int length = individual.length;

Random r = new Random(System.currentTimeMillis());

individual[r.nextInt(length)] ^= false;

}

// 轮盘法选择下一代,并返回当代最高的适应度值

public double selection() {

boolean[][] next_generation = new boolean[population][]; // 下一代

int length = gene_len * chrom_len;

for (int i = 0; i population; i++)

next_generation[i] = new boolean[length];

double[] cumulation = new double[population];

int best_index = 0;

double max_fitness = getFitness(individuals.get(best_index));

cumulation[0] = max_fitness;

for (int i = 1; i population; i++) {

double fit = getFitness(individuals.get(i));

cumulation[i] = cumulation[i - 1] + fit;

// 寻找当代的最优个体

if (fit max_fitness) {

best_index = i;

max_fitness = fit;

}

}

Random rand = new Random(System.currentTimeMillis());

for (int i = 0; i population; i++)

next_generation[i] = individuals.get(findByHalf(cumulation,

rand.nextDouble() * cumulation[population - 1]));

// 把当代的最优个体及其适应度放到best_individual中

BI bi = new BI(max_fitness, individuals.get(best_index));

// printPath(individuals.get(best_index));

//System.out.println(max_fitness);

best_individual.add(bi);

// 新一代作为当前代

for (int i = 0; i population; i++)

individuals.set(i, next_generation[i]);

return max_fitness;

}

// 折半查找

public int findByHalf(double[] arr, double find) {

if (find  0 || find == 0 || find arr[arr.length - 1])

return -1;

int min = 0;

int max = arr.length - 1;

int medium = min;

do {

if (medium == (min + max) / 2)

break;

medium = (min + max) / 2;

if (arr[medium] find)

min = medium;

else if (arr[medium] find)

max = medium;

else

return medium;

} while (min max);

return max;

}

// 计算适应度

public double getFitness(boolean[] individual) {

int length = individual.length;

// 记录当前的位置,入口点是（1,0）

int x = 1;

int y = 0;

// 根据染色体中基因的指导向前走

for (int i = 0; i length; i++) {

boolean b1 = individual[i];

boolean b2 = individual[++i];

// 00向左走

if (b1 == false  b2 == false) {

if (x  0  labyrinth.map[y][x - 1] == true) {

x--;

}

}

// 01向右走

else if (b1 == false  b2 == true) {

if (x + 1  width labyrinth.map[y][x + 1] == true) {

x++;

}

}

// 10向上走

else if (b1 == true  b2 == false) {

if (y  0  labyrinth.map[y - 1][x] == true) {

y--;

}

}

// 11向下走

else if (b1 == true  b2 == true) {

if (y + 1  height labyrinth.map[y + 1][x] == true) {

y++;

}

}

}

int n = Math.abs(x - labyrinth.x_end) + Math.abs(y -labyrinth.y_end) + 1;

//      if(n==1)

//          printPath(individual);

return 1.0 / n;

}

// 运行遗传算法

public boolean run() {

// 初始化种群

initPopulation();

Random rand = new Random(System.currentTimeMillis());

boolean success = false;

while (iter_limit--  0) {

// 打乱种群的顺序

Collections.shuffle(individuals);

for (int i = 0; i population - 1; i += 2) {

// 交叉

if (rand.nextDouble() cross_ratio) {

cross(individuals.get(i), individuals.get(i + 1));

}

// 变异

if (rand.nextDouble() muta_ratio) {

mutation(individuals.get(i));

}

}

// 种群更替

if (selection() == 1) {

success = true;

break;

}

}

return success;

}

//  public static void main(String[] args) {

//      GA ga = new GA(8, 8);

//      if (!ga.run()) {

//          System.out.println("没有找到走出迷宫的路径.");

//      } else {

//          int gen = ga.best_individual.size();

//          boolean[] individual = ga.best_individual.get(gen - 1).indv;

//          System.out.println(ga.getPath(individual));

//      }

//  }

// 根据染色体打印走法

public String getPath(boolean[] individual) {

int length = individual.length;

int x = 1;

int y = 0;

LinkedListString stack=new LinkedListString();

for (int i = 0; i length; i++) {

boolean b1 = individual[i];

boolean b2 = individual[++i];

if (b1 == false  b2 == false) {

if (x  0  labyrinth.map[y][x - 1] == true) {

x--;

if(!stack.isEmpty() stack.peek()=="右")

stack.poll();

else

stack.push("左");

}

} else if (b1 == false  b2 == true) {

if (x + 1  width labyrinth.map[y][x + 1] == true) {

x++;

if(!stack.isEmpty() stack.peek()=="左")

stack.poll();

else

stack.push("右");

}

} else if (b1 == true  b2 == false) {

if (y  0  labyrinth.map[y - 1][x] == true) {

y--;

if(!stack.isEmpty() stack.peek()=="下")

stack.poll();

else

stack.push("上");

}

} else if (b1 == true  b2 == true) {

if (y + 1  height labyrinth.map[y + 1][x] == true) {

y++;

if(!stack.isEmpty() stack.peek()=="上")

stack.poll();

else

stack.push("下");

}

}

}

StringBuilder sb=new StringBuilder(length/4);

IteratorString iter=stack.descendingIterator();

while(iter.hasNext())

sb.append(iter.next());

return sb.toString();

}

}

A*算法java实现

代码实现(Java)

1. 输入

(1) 代表地图二值二维数组(0表示可通路，1表示路障)

int[][] maps = {

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }

};123456789123456789

(2) 按照二维数组的特点，坐标原点在左上角，所以y是高，x是宽，y向下递增，x向右递增，我们将x和y封装成一个类，好传参，重写equals方法比较坐标(x,y)是不是同一个。

public class Coord

{

public int x;

public int y;

public Coord(int x, int y)

{

this.x = x;

this.y = y;

}

@Override

public boolean equals(Object obj)

{

if (obj == null) return false;

if (obj instanceof Coord)

{

Coord c = (Coord) obj;

return x == c.x y == c.y;

}

return false;

}

}12345678910111213141516171819202122231234567891011121314151617181920212223

(3) 封装路径结点类，字段包括：坐标、G值、F值、父结点，实现Comparable接口，方便优先队列排序。

public class Node implements Comparable

{

public Coord coord; // 坐标

public Node parent; // 父结点

public int G; // G：是个准确的值，是起点到当前结点的代价

public int H; // H：是个估值，当前结点到目的结点的估计代价

public Node(int x, int y)

{

this.coord = new Coord(x, y);

}

public Node(Coord coord, Node parent, int g, int h)

{

this.coord = coord;

this.parent = parent;

G = g;

H = h;

}

@Override

public int compareTo(Node o)

{

if (o == null) return -1;

if (G + H o.G + o.H)

return 1;

else if (G + H o.G + o.H) return -1;

return 0;

}

}1234567891011121314151617181920212223242526272829303112345678910111213141516171819202122232425262728293031

(4) 最后一个数据结构是A星算法输入的所有数据，封装在一起，传参方便。:grin:

public class MapInfo

{

public int[][] maps; // 二维数组的地图

public int width; // 地图的宽

public int hight; // 地图的高

public Node start; // 起始结点

public Node end; // 最终结点

public MapInfo(int[][] maps, int width, int hight, Node start, Node end)

{

this.maps = maps;

this.width = width;

this.hight = hight;

this.start = start;

this.end = end;

}

}12345678910111213141516171234567891011121314151617

2. 处理

(1) 在算法里需要定义几个常量来确定：二维数组中哪个值表示障碍物、二维数组中绘制路径的代表值、计算G值需要的横纵移动代价和斜移动代价。

public final static int BAR = 1; // 障碍值

public final static int PATH = 2; // 路径

public final static int DIRECT_VALUE = 10; // 横竖移动代价

public final static int OBLIQUE_VALUE = 14; // 斜移动代价12341234

(2) 定义两个辅助表：Open表和Close表。Open表的使用是需要取最小值，在这里我们使用Java工具包中的优先队列PriorityQueue，Close只是用来保存结点，没其他特殊用途，就用ArrayList。

Queue openList = new PriorityQueue(); // 优先队列(升序)

List closeList = new ArrayList();1212

(3) 定义几个布尔判断方法：最终结点的判断、结点能否加入open表的判断、结点是否在Close表中的判断。

/**

* 判断结点是否是最终结点

*/

private boolean isEndNode(Coord end,Coord coord)

{

return coord != null end.equals(coord);

}

/**

* 判断结点能否放入Open列表

*/

private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)

{

// 是否在地图中

if (x 0 || x = mapInfo.width || y 0 || y = mapInfo.hight) return false;

// 判断是否是不可通过的结点

if (mapInfo.maps[y][x] == BAR) return false;

// 判断结点是否存在close表

if (isCoordInClose(x, y)) return false;

return true;

}

/**

* 判断坐标是否在close表中

*/

private boolean isCoordInClose(Coord coord)

{

return coord!=nullisCoordInClose(coord.x, coord.y);

}

/**

* 判断坐标是否在close表中

*/

private boolean isCoordInClose(int x, int y)

{

if (closeList.isEmpty()) return false;

for (Node node : closeList)

{

if (node.coord.x == x node.coord.y == y)

{

return true;

}

}

return false;

}1234567891011121314151617181920212223242526272829303132333435363738394041424344454612345678910111213141516171819202122232425262728293031323334353637383940414243444546

(4) 计算H值，“曼哈顿” 法，坐标分别取差值相加

private int calcH(Coord end,Coord coord)

{

return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);

}12341234

(5) 从Open列表中查找结点

private Node findNodeInOpen(Coord coord)

{

if (coord == null || openList.isEmpty()) return null;

for (Node node : openList)

{

if (node.coord.equals(coord))

{

return node;

}

}

return null;

}123456789101112123456789101112

(6) 添加邻结点到Open表

/**

* 添加所有邻结点到open表

*/

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)

{

int x = current.coord.x;

int y = current.coord.y;

// 左

addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);

// 上

addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);

// 右

addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);

// 下

addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);

// 左上

addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);

// 右上

addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);

// 右下

addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);

// 左下

addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);

}

/**

* 添加一个邻结点到open表

*/

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)

{

if (canAddNodeToOpen(mapInfo,x, y))

{

Node end=mapInfo.end;

Coord coord = new Coord(x, y);

int G = current.G + value; // 计算邻结点的G值

Node child = findNodeInOpen(coord);

if (child == null)

{

int H=calcH(end.coord,coord); // 计算H值

if(isEndNode(end.coord,coord))

{

child=end;

child.parent=current;

child.G=G;

child.H=H;

}

else

{

child = new Node(coord, current, G, H);

}

openList.add(child);

}

else if (child.G G)

{

child.G = G;

child.parent = current;

// 重新调整堆

openList.add(child);

}

}

}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606112345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061

(7) 回溯法绘制路径

private void drawPath(int[][] maps, Node end)

{

if(end==null||maps==null) return;

System.out.println("总代价：" + end.G);

while (end != null)

{

Coord c = end.coord;

maps[c.y][c.x] = PATH;

end = end.parent;

}

}12345678910111234567891011

(8) 开始算法，循环移动结点寻找路径，设定循环结束条件，Open表为空或者最终结点在Close表

public void start(MapInfo mapInfo)

{

if(mapInfo==null) return;

// clean

openList.clear();

closeList.clear();

// 开始搜索

openList.add(mapInfo.start);

moveNodes(mapInfo);

}

/**

* 移动当前结点

*/

private void moveNodes(MapInfo mapInfo)

{

while (!openList.isEmpty())

{

if (isCoordInClose(mapInfo.end.coord))

{

drawPath(mapInfo.maps, mapInfo.end);

break;

}

Node current = openList.poll();

closeList.add(current);

addNeighborNodeInOpen(mapInfo,current);

}

}

单元和区域和数值，，，中的最大