我正在尝试开发java程序，用于在加权图中使用遗传算法查找最短路径。我在基于该算法的编码中遇到困难。有人可以告诉我这个问题的示例代码吗？任何语言都可以。任何可能对这个问题有帮助的信息(例如图书馆或其他信息)也可以。现在最重要的是测试根据该算法找到最短路径的时间，我需要在作业截止日期之前找到答案。所以如果有人可以帮助我，请。
我是基于java进行编码的，主要在交叉和变异过程中遇到困难。定义适应度函数也是一个问题。
最佳答案
这是最短路径遗传算法的 Java 示例
package ga;
import java.util.ArrayList;
import java.util.Arrays;
public class GA {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//computation time
long start = System.nanoTime();
//population size
int populationSize = 30;
//Number of Cities
int numCities = 15;
//Mutation rate
double mutationRate = 0.05;
//Crossover Rate
double crossoverRate = 0.8;
//Choose File path or if false randomly created Path
boolean useFile = false;
//Name the file to be used
String fileName = "Data.txt";
//Current Number of Generations
int numberOfGenerations = 0;
//Stop Condition
int stopAt=2500;
//Population
Population pop;
//use GA or Brute Force
boolean GAuse=true;
//Selecting File mode or Random Mode
if (useFile == false) {
pop = new Population(populationSize, numCities, crossoverRate, mutationRate);
} else {
FileReader file = new FileReader(fileName);
numCities=file.getNumCities();
crossoverRate=file.getCrossoverRate();
mutationRate=file.getMutationRate();
populationSize=file.getCities().length;
Path p = new Path(file.getNumCities());
p.setPath(file.getCities());
pop = new Population(populationSize, numCities, p,crossoverRate ,mutationRate );
}
if(GAuse==true){
//Sorting the population from Finess / Evaluating
pop.FitnessOrder();
//Prints each path ID/Cost/Fitness/City order(with coordinates)
for (int i = 0; i < pop.getPopulation().length; i++) {
System.out.println("Path ID: "+i+" | Cost: "+pop.getPopulation()[i].getCost()+" | Fitness: "+pop.getPopulation()[i].getFitness()+"%");
System.out.print("Path is: ");
for (int j = 0; j < pop.getPopulation()[i].getPath().length; j++) {
System.out.print(pop.getPopulation()[i].getPath()[j].getId() +"("+pop.getPopulation()[i].getPath()[j].getX()+","+pop.getPopulation()[i].getPath()[j].getY()+") ");
}System.out.println("\n -----------------------------------------------------");
}
//Start looking for possible solution
while (numberOfGenerations !=stopAt) {
//Select / Crossover
while (pop.Mate() == false);
//Mutate
for (int i = 0; i < pop.getNextGen().length; i++) {
pop.getNextGen()[i].setPath(pop.Mutation(pop.getNextGen()[i].getPath()));
}
//Setting the new Generation to current Generation
pop.setPopulation(pop.getNextGen());
pop.setDone(0);
//Sorting the new population from Finess / Evaluating
pop.FitnessOrder();
//Incremente number of Generations
numberOfGenerations++;
}
//Prints out the fitness of each path
double valor=0;
for (int i = 0; i < pop.getPopulation().length; i++) {
valor += pop.getPopulation()[i].getFitness();
System.out.println("Value of Fitness: "+pop.getPopulation()[i].getFitness()+"%");
}
System.out.println("");
System.out.println("Total Fitness: "+valor+"%");
System.out.println("\n-----------------------------------------------");
//Prints each path ID/Cost/Fitness/City order(with coordinates)
for (int i = 0; i < pop.getPopulation().length; i++) {
System.out.println("Path ID: "+i+" | Cost: "+pop.getPopulation()[i].getCost()+" | Fitness: "+pop.getPopulation()[i].getFitness()+"%");
System.out.print("Path is: ");
for (int j = 0; j < pop.getPopulation()[i].getPath().length; j++) {
System.out.print(pop.getPopulation()[i].getPath()[j].getId() +"("+pop.getPopulation()[i].getPath()[j].getX()+","+pop.getPopulation()[i].getPath()[j].getY()+") ");
}System.out.println("\n -----------------------------------------------------");
}
}
else{//USING BRUTE FORTE METHOD
FileReader file = new FileReader(fileName);
ArrayList<City> cities = new ArrayList<City>();
for (int i = 0; i <file.getNumCities(); i++) {
cities.add(file.getCities()[i]);
}
ArrayList<City> best = new ArrayList<City>();
Permutations permu = new Permutations();
permu.permutations(cities);
System.out.print("The shortest path is: ");
for (int i = 0; i < permu.getBest().size(); i++) {
System.out.print(permu.getBest().get(i).getId()+"("+permu.getBest().get(i).getX()+","+permu.getBest().get(i).getY()+")");
}
System.out.println("");
System.out.println("It would Cost: "+permu.getCost());
}
long elapsedTime = System.nanoTime() - start;
System.out.println("Algorithm took: "+elapsedTime+" nano seconds to find a solution");
}
}
package ga;
import java.util.ArrayList;
public class Permutations {
private int cost=999999;
private ArrayList<City> best;
public void permutations(ArrayList<City> list){
permutations(null, list, null);
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public ArrayList<City> getBest() {
return best;
}
public void setBest(ArrayList<City> best) {
this.best = best;
}
public ArrayList<City> permutations(ArrayList<City> prefix, ArrayList<City> suffix, ArrayList<ArrayList<City>> output){
if(prefix == null)
prefix = new ArrayList<City>();
if(output == null)
output = new ArrayList<ArrayList<City>>();
if(suffix.size() == 1){
ArrayList<City> newElement = new ArrayList<City>(prefix);
newElement.addAll(suffix);
int costNow=cost(newElement);
if(costNow<this.cost){
best=newElement;
this.cost=costNow;
}
return best;
}
for(int i = 0; i < suffix.size(); i++){
ArrayList<City> newPrefix = new ArrayList<City>(prefix);
newPrefix.add(suffix.get(i));
ArrayList<City> newSuffix = new ArrayList<City>(suffix);
newSuffix.remove(i);
permutations(newPrefix,newSuffix,output);
}
return best;
}
public int cost(ArrayList<City> path){
int cost=0;
int i=0;
while(i<path.size()-1){
cost+=path.get(i).distance(path.get(i+1).getX(),path.get(i+1).getY());
i++;
}
cost+=path.get(path.size()-1).distance(path.get(0).getX(), path.get(0).getY());
return cost;
}
}
package ga;
import java.util.Random;
public class Path implements Comparable {
private City [] path;
private int numCities;
private int cost;
private int fitness;
public Path(int numCities) {
this.numCities = numCities;
CreatePath();
cost =0;
calculateCost();
fitness =0;
}
public void calculateCost(){
cost=0;
int i=0;
while(i<numCities-1){
cost+=path[i].distance(path[i+1].getX(),path[i+1].getY());
i++;
}
cost+=path[path.length-1].distance(path[0].getX(), path[0].getY());
}
public int getFitness() {
return fitness;
}
public void setFitness(int fitness) {
this.fitness = fitness;
}
public int getCost() {
return cost;
}
public void setCost(int distance) {
this.cost = distance;
}
/* Overload compareTo method */
public int compareTo(Object obj){
Path tmp = (Path) obj;
if(this.cost < tmp.cost){
return 1;
}
else if(this.cost > tmp.cost){
return -1;
}
else{
return 0;
}
}
public void CreatePath(){
path= new City[numCities];
for (int i = 0; i < path.length; i++) {
path[i]=new City(i,RandomNum(1, 99),RandomNum(1, 99));
}
}
public int RandomNum(int min, int max){
return min+ (new Random()).nextInt(max-min);
}
public City[] getPath() {
return path;
}
public void setPath(City[] path) {
this.path = path;
calculateCost();
}
public int getNumCities() {
return numCities;
}
public void setNumCities(int numCities) {
this.numCities = numCities;
}
}
package ga;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
public class FileReader {
private int numCities;
private double mutationRate;
private City[] cities;
private int curLine;
private StringTokenizer st;
private int arrayCount;
private int x, y;
private double crossoverRate;
private String fileName;
public FileReader(String fileName) {
numCities = 0;
mutationRate = 0;
City[] cities = new City[0];
curLine = 1;
arrayCount = 0;
this.fileName=fileName;
read();
}
public int getNumCities() {
return numCities;
}
public void setNumCities(int numCities) {
this.numCities = numCities;
}
public double getMutationRate() {
return mutationRate;
}
public void setMutationRate(double mutationRate) {
this.mutationRate = mutationRate;
}
public City[] getCities() {
return cities;
}
public void setCities(City[] cities) {
this.cities = cities;
}
public int getCurLine() {
return curLine;
}
public void setCurLine(int curLine) {
this.curLine = curLine;
}
public StringTokenizer getSt() {
return st;
}
public void setSt(StringTokenizer st) {
this.st = st;
}
public int getArrayCount() {
return arrayCount;
}
public void setArrayCount(int arrayCount) {
this.arrayCount = arrayCount;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public void read() {
try {
BufferedReader in = new BufferedReader(new java.io.FileReader("./"+fileName));
String line;
try {
while ((line = in.readLine()) != null) {
if (curLine == 1) {
st = new StringTokenizer(line, "=");
st.nextToken();
numCities = Integer.parseInt(st.nextToken());
cities = new City[numCities];
} else if (curLine == 2) {
st = new StringTokenizer(line, "=");
st.nextToken();
mutationRate = Double.parseDouble(st.nextToken());
}else if(curLine==3){
st = new StringTokenizer(line, "=");
st.nextToken();
crossoverRate = Double.parseDouble(st.nextToken());
}
else {
st = new StringTokenizer(line, "|");
st.nextToken();
String a = st.nextToken();
StringTokenizer stmp = new StringTokenizer(a, "=");
stmp.nextToken();
x = Integer.parseInt(stmp.nextToken());
String l = st.nextToken();
stmp = new StringTokenizer(l, "=");
stmp.nextToken();
y = Integer.parseInt(stmp.nextToken());
cities[arrayCount] = new City(arrayCount, x, y);
arrayCount++;
}
curLine++;
}
} catch (Exception e) {
}
} catch (FileNotFoundException e) {
System.out.println("File not found!!");
}
}
public double getCrossoverRate() {
return crossoverRate;
}
public void setCrossoverRate(double crossoverRate) {
this.crossoverRate = crossoverRate;
}
}
package ga;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
public class Population {
private int populationSize;
private int numCities;
private Path[] population;
private double crossoverRate;
private City[] child1;
private City[] child2;
private double mutationRate;
private Path[] nextGen;
private int done;
public Population(int populationSize, int numCities, double crossoverRage, double mutationRate) {
this.populationSize = populationSize;
this.numCities = numCities;
population = new Path[populationSize];
this.crossoverRate = crossoverRage;
this.mutationRate = mutationRate;
this.nextGen = new Path[populationSize];
Path p = new Path(numCities);
done = 0;
CreatePopulation(p);
}
public Population(int populationSize, int numCities, Path path, double crossoverRage, double mutationRate) {
this.populationSize = populationSize;
this.numCities = numCities;
this.crossoverRate = crossoverRage;
population = new Path[populationSize];
this.mutationRate = mutationRate;
this.nextGen = new Path[populationSize];
done = 0;
CreatePopulation(path);
}
public void CreatePopulation(Path p) {
int i = 0;
while (i < populationSize) {
City[] tmpCity = new City[numCities];
for (int j = 0; j < tmpCity.length; j++) {
tmpCity[j] = p.getPath()[j];
}
Collections.shuffle(Arrays.asList(tmpCity));
Path tmpPath = new Path(numCities);
tmpPath.setPath(tmpCity);
population[i] = tmpPath;
i++;
}
}
public int SelectParent() {
int total = 0;
//Selecting parents
int totalCost = calculateTotalFitness();
int fit = RandomNum(0, totalCost);
int value = 0;
for (int i = 0; i < population.length; i++) {
value += population[i].getFitness();
if (fit <= value) {
return i;
}//if(fit<=value){
}
return -1;
}
public boolean Mate() {
//Generate a random number to check if the parents cross
int check = RandomNum(0, 100);
int parent1 = SelectParent();
int parent2 = SelectParent();
while (parent1 == parent2) {
parent2 = SelectParent();
}
//check if there is going to be a crossover
if (check <= (crossoverRate * 100)) {
int crossoverPoint = RandomNum(0, population[parent1].getPath().length - 1);
child1 = new City[numCities];
child2 = new City[numCities];
//crossing over
for (int i = 0; i < crossoverPoint; i++) {
child1[i] = population[parent2].getPath()[i];
child2[i] = population[parent1].getPath()[i];
}
for (int i = crossoverPoint; i < numCities; i++) {
child1[i] = population[parent1].getPath()[i];
child2[i] = population[parent2].getPath()[i];
}
//Rearrange childs considering city repetition
int cityChild1;
int cityChild2;
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
for (int i = 0; i < crossoverPoint; i++) {
cityChild1 = child1[i].getId();
cityChild2 = child2[i].getId();
//Get the positions of repeated values
for (int j = crossoverPoint; j < numCities; j++) {
if (cityChild1 == child1[j].getId()) {
list1.add(j);
}
if (cityChild2 == child2[j].getId()) {
list2.add(j);
}
}
}
//Find the missing values
for (int i = 0; i < numCities; i++) {
boolean found = false;
//Fixing Child1
for (int j = 0; j < numCities; j++) {
if (population[parent2].getPath()[i] == child1[j]) {
found = true;
break;
}
}
if (found == false) {
child1[list1.remove(list1.size() - 1)] = population[parent2].getPath()[i];
}
found = false;
//Fixing Child2
for (int j = 0; j < numCities; j++) {
if (population[parent1].getPath()[i] == child2[j]) {
found = true;
break;
}
}
if (found == false) {
child2[list2.remove(list2.size() - 1)] = population[parent1].getPath()[i];
}
}
// System.out.print("Parent 1: ");
// for (int i = 0; i < numCities; i++) {
// if (i == crossoverPoint) {
// System.out.print("| ");
// }
// System.out.print(population[parent1].getPath()[i].getId() + " ");
// }
// System.out.print("\nParent 2: ");
// for (int i = 0; i < numCities; i++) {
// if (i == crossoverPoint) {
// System.out.print("| ");
// }
// System.out.print(population[parent2].getPath()[i].getId() + " ");
// }
// System.out.print("\nChild 1: ");
// for (int i = 0; i < numCities; i++) {
// if (i == crossoverPoint) {
// System.out.print("| ");
// }
// System.out.print(child1[i].getId() + " ");
// }
// System.out.print("\nChild 2: ");
// for (int i = 0; i < numCities; i++) {
// if (i == crossoverPoint) {
// System.out.print("| ");
// }
// System.out.print(child2[i].getId() + " ");
// }
// System.out.println("");
//
// //Repeated Values
// for (int i = 0; i < list1.size(); i++) {
// System.out.print(list1.get(i) + " ");
// }
// System.out.println("");
// for (int i = 0; i < list2.size(); i++) {
// System.out.print(list2.get(i) + " ");
// }
if (AddToGenerationCheckFull(child1, child2) == false) {
return false;
} else {
return true;
}
} else {
if (AddToGenerationCheckFull(population[parent1].getPath(), population[parent1].getPath()) == false) {
return false;
} else {
return true;
}
}
}
public int getDone() {
return done;
}
public void setDone(int done) {
this.done = done;
}
public boolean AddToGenerationCheckFull(City[] child1, City[] child2) {
if (done == populationSize) {
return true;
}
Path newGenChild1 = new Path(numCities);
Path newGenChild2 = new Path(numCities);
newGenChild1.setPath(child1);
newGenChild2.setPath(child2);
if (done < populationSize - 2) {
this.nextGen[done] = newGenChild1;
this.nextGen[done + 1] = newGenChild2;
this.done += 2;
return false;
} else if (done == populationSize - 2) {
this.nextGen[done] = newGenChild1;
this.nextGen[done + 1] = newGenChild2;
done += 2;
return true;
} else {
this.nextGen[done] = newGenChild1;
done += 1;
return true;
}
}
public Path[] getNextGen() {
return nextGen;
}
public void setNextGen(Path[] nextGen) {
this.nextGen = nextGen;
}
public City[] Mutation(City[] child) {
int check = RandomNum(0, 100);
//Checks if its going to mutate
if (check <= (mutationRate * 100)) {
//finds the 2 cities that "mutate"
int point1 = RandomNum(0, numCities - 1);
int point2 = RandomNum(0, numCities - 1);
while (point2 == point1) {
point2 = RandomNum(0, numCities - 1);
}
//Cities are switched as result of mutation
City city1 = child[point1];
City city2 = child[point2];
child[point1] = city2;
child[point2] = city1;
}
return child;
}
public int RandomNum(int min, int max) {
return min + (new Random()).nextInt(max - min);
}
public void FitnessOrder() {
Arrays.sort(population);
// double cost = calculateTotalCost();
for (int i = 0; i < population.length; i++) {
// double total = cost - population[i].getCost();
// double fitness = (total * 100) / cost;
// fitness = 100 - fitness;
// population[i].setFitness(fitness);
int lol = 100000 / (population[i].getCost() + 1);
population[i].setFitness(lol);
// System.out.println("Total: "+total + " "+" Cost: "+cost+" "+" Fitness: "+fitness+"%" );
}
}
public int calculateTotalFitness() {
int cost = 0;
for (int i = 0; i < population.length; i++) {
cost += population[i].getFitness();
}
return cost;
}
public double getCrossoverRate() {
return crossoverRate;
}
public void setCrossoverRate(double crossoverRage) {
this.crossoverRate = crossoverRage;
}
public Path[] getPopulation() {
return population;
}
public void setPopulation(Path[] population) {
this.population = population;
}
public int getPopulationSize() {
return populationSize;
}
public void setPopulationSize(int populationSize) {
this.populationSize = populationSize;
}
public int getNumCities() {
return numCities;
}
public void setNumCities(int numCities) {
this.numCities = numCities;
}
}
package ga;
public class City {
private int x;
private int y;
private int id;
public City(int id,int x, int y){
this.x=x;
this.y=y;
this.id=id;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int distance(int xOther,int yOther){
return (int) Math.sqrt(((this.x-xOther)*(this.x-xOther))+((this.y-yOther)*(this.y-yOther)));
}
}
关于java - 用遗传算法寻找最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56854983/