Java - TSP con algorítmos genéticos y un greedy para la población inicial

   
Vista:

TSP con algorítmos genéticos y un greedy para la población inicial

Publicado por Carlos (1 intervención) el 02/08/2012 01:23:08
Hola:

Necesito en progrmar en java un TSP con un algortítmo genético, esa parte está ok me la entregó mi profesor, el problema es que tengo que implementar un greedy para la solución inicial de la población, encontré en la red un código para eso y no se bien como ensamblarlo. Alguien que me pueda ayudar?

El código que está aquí quisiera implementarlo como un Greedy:

public void crearPopulacionInicialGreedy(int chromosomesize)
{
//crear una populacion inicial desde permutaciones de un solucion.
for (int i=0; i<individuals.length; i++) {

TSPChromosome c=new TSPChromosome(chromosomesize);
for (int j=0; j<c.getSize(); j++)
c.setGene(j,j);
for (int j=0; j<c.getSize(); j++) {
int pos1 = r.nextInt(c.getSize()-1)+1;
int pos2 = r.nextInt(c.getSize()-1)+1;
c.swap(pos1,pos2);
}

setIndividual(c,i);
}
}



Y este es el código del Greedy que encontré en La red:


//////////////////////////////////////////////////////////////////////////////////////////////////
// File Name: Population.cs
// Date: 06/01/2006
// Copyright (c) 2006 Michael LaLena. All rights reserved. (www.lalena.com)
// Permission to use, copy, modify, and distribute this Program and its documentation,
// if any, for any purpose and without fee is hereby granted, provided that:
// (i) you not charge any fee for the Program, and the Program not be incorporated
// by you in any software or code for which compensation is expected or received;
// (ii) the copyright notice listed above appears in all copies;
// (iii) both the copyright notice and this Agreement appear in all supporting documentation; and
// (iv) the name of Michael LaLena or lalena.com not be used in advertising or publicity
// pertaining to distribution of the Program without specific, written prior permission.
///////////////////////////////////////////////////////////////////////////////////////////////////
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace Tsp
{
class Population : List<Tour>
{
/// <summary>
/// Private copy of the best tour found so far by the Genetic Algorithm.
/// </summary>
private Tour bestTour = null;
/// <summary>
/// The best tour found so far by the Genetic Algorithm.
/// </summary>
public Tour BestTour
{
set
{
bestTour = value;
}
get
{
return bestTour;
}
}

/// <summary>
/// Create the initial set of random tours.
/// </summary>
/// <param name="populationSize">Number of tours to create.</param>
/// <param name="cityList">The list of cities in this tour.</param>
/// <param name="rand">Random number generator. We pass around the same random number generator, so that results between runs are consistent.</param>
/// <param name="chanceToUseCloseCity">The odds (out of 100) that a city that is known to be close will be used in any given link.</param>
public void CreateRandomPopulation(int populationSize, Cities cityList, Random rand, int chanceToUseCloseCity)
{
int firstCity, lastCity, nextCity;

for (int tourCount = 0; tourCount < populationSize; tourCount++)
{
Tour tour = new Tour(cityList.Count);

// Create a starting point for this tour
firstCity = rand.Next(cityList.Count);
lastCity = firstCity;

for (int city = 0; city < cityList.Count - 1; city++)
{
do
{
// Keep picking random cities for the next city, until we find one we haven't been to.
if ((rand.Next(100) < chanceToUseCloseCity) && ( cityList[city].CloseCities.Count > 0 ))
{
// 75% chance will will pick a city that is close to this one
nextCity = cityList[city].CloseCities[rand.Next(cityList[city].CloseCities.Count)];
}
else
{
// Otherwise, pick a completely random city.
nextCity = rand.Next(cityList.Count);
}
// Make sure we haven't been here, and make sure it isn't where we are at now.
} while ((tour[nextCity].Connection2 != -1) || (nextCity == lastCity));

// When going from city A to B, [1] on A = B and [1] on city B = A
tour[lastCity].Connection2 = nextCity;
tour[nextCity].Connection1 = lastCity;
lastCity = nextCity;
}

// Connect the last 2 cities.
tour[lastCity].Connection2 = firstCity;
tour[firstCity].Connection1 = lastCity;

tour.DetermineFitness(cityList);

Add(tour);

if ((bestTour == null) || (tour.Fitness < bestTour.Fitness))
{
BestTour = tour;
}
}
}
}
}
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder