# Changeset 12228

Ignore:
Timestamp:
03/19/15 17:16:39 (7 years ago)
Message:

#2221: Local improvement operator for VNS

Location:
branches/PTSP
Files:
6 edited

Unmodified
Removed
• ## branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs

 r12219 for (int i = 0; i < p.Length - 1; i++) { for (int j = i + 1; j < p.Length - 1; j++) { double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value; double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]]; for (int k = i + 1; k < j; k++) { sum1 = sum1 * (1 - ProbabilityMatrix[p[k]].Value); sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]); } A[i, j - 1] = sum1; for (int j = 0; j < p.Length - 1; j++) { for (int i = 0; i < j; i++) { double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value; double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]]; for (int k = j + 1; k < p.Length - 1; k++) { sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value); sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]); } for (int k = 1; k < i; k++) { sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value); sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]); } B[i, j] = sum2;
• ## branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

 r12219 Operators.Add(new PTSPEstimatedInversionMovePathEvaluator()); Operators.Add(new PTSPEstimatedInsertionEvaluator()); Operators.Add(new PTSPExhaustiveInversionLocalImprovement()); Operators.Add(new PTSPExhaustiveInsertionLocalImprovement()); Encoding.ConfigureOperators(Operators.OfType()); } realizations.Add(new ItemList()); for (int j = 0; j < data.Dimension; j++) { if (ProbabilityMatrix[j].Value > r.NextDouble()) { if (ProbabilityMatrix[j] > r.NextDouble()) { realizations.ElementAt(i).Add(new IntValue(1)); } else { } foreach (var op in Operators.OfType()) { op.RealizationsParameter.Value = realizations; } foreach (var op in Operators.OfType()) { op.RealizationsParameter.Value = realizations; }
• ## branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

 r12219 prompt4AnyCPU
• ## branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs

 r12219 public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator { private static ItemList probabilities; private static DoubleArray probabilities; private static DoubleMatrix A; private static DoubleMatrix B; } public IValueParameter> ProbabilitiesParameter { get { return (IValueParameter>)Parameters["Probabilities"]; } public IValueParameter ProbabilitiesParameter { get { return (IValueParameter)Parameters["Probabilities"]; } } case 1: if (j == i + 1) { return (1/(1-probabilities[i+1].Value))*A[i,2]+(1 - probabilities[i].Value)*(A[i+1,1]-A[i+1,probabilities.Capacity-1]); return (1/(1-probabilities[i+1]))*A[i,2]+(1 - probabilities[i])*(A[i+1,1]-A[i+1,probabilities.Length-1]); } else if (i == j) { return A[i,1]; } else { // Equation 25 return ((1 - probabilities[i].Value) / (1 - probabilities[j].Value)) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i].Value) * (1); return ((1 - probabilities[i]) / (1 - probabilities[j])) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i]) * (1); } case 2: if (j == i + 1) { return (1 - probabilities[i + 1].Value) * (B[i, 1] - B[i, probabilities.Capacity - 1]) + (1 / (1 - probabilities[i].Value)) * (B[i + 1, 2]); return (1 - probabilities[i + 1]) * (B[i, 1] - B[i, probabilities.Length - 1]) + (1 / (1 - probabilities[i])) * (B[i + 1, 2]); } else if (i == j) { return B[i,1]; case 3: if (j == i + 1) { return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Capacity - 1] + B[i, 1] - B[i, probabilities.Capacity - 1] + B[i + 1, 2]; return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Length - 1] + B[i, 1] - B[i, probabilities.Length - 1] + B[i + 1, 2]; } else if (i == j) { return A[i,1]+B[i,1];
• ## branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

 r12219 public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem, IStorableContent, IProblemInstanceConsumer { private static readonly int DistanceMatrixSizeLimit = 1000; #region Parameter Properties public OptionalValueParameter CoordinatesParameter { get { return (OptionalValueParameter)Parameters["BestKnownSolution"]; } } public OptionalValueParameter> ProbabilityMatrixParameter { get { return (OptionalValueParameter>)Parameters["ProbabilityMatrix"]; } public ValueParameter ProbabilityMatrixParameter { get { return (ValueParameter)Parameters["ProbabilityMatrix"]; } } public ValueParameter SampleSizeParameter { set { BestKnownSolutionParameter.Value = value; } } public ItemList ProbabilityMatrix { public DoubleArray ProbabilityMatrix { get { return ProbabilityMatrixParameter.Value; } set { ProbabilityMatrixParameter.Value = value; } Parameters.Add(new ValueParameter("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true))); Parameters.Add(new OptionalValueParameter("BestKnownSolution", "The best known solution of this TSP instance.")); Parameters.Add(new OptionalValueParameter>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities.")); Parameters.Add(new ValueParameter("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities.")); Coordinates = new DoubleMatrix(new double[,] { { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 }, { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 }, { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 }, { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 } }); ProbabilityMatrix = new DoubleArray(new double[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}); } public virtual void Load(TSPData data) { if (data.Coordinates == null && data.Distances == null) throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!"); if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att || data.DistanceMeasure == DistanceMeasure.Manhattan || data.DistanceMeasure == DistanceMeasure.Maximum)) throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix."); if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2) throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates."); Name = data.Name; Description = data.Description; bool clearCoordinates = false, clearDistanceMatrix = false; if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0) Coordinates = new DoubleMatrix(data.Coordinates); else clearCoordinates = true; // reset them after assigning the evaluator if (clearCoordinates) Coordinates = null; if (clearDistanceMatrix) DistanceMatrix = null; DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix()); // Get Probabilities of cities using random with seed from hash function on the Name of the instance ProbabilityMatrix = new ItemList(data.Dimension); ProbabilityMatrix = new DoubleArray(data.Dimension); Random r = new Random(data.Name.GetHashCode()); for (int i = 0; i < data.Dimension; i++) { ProbabilityMatrix.Add(new DoubleValue(r.NextDouble())); ProbabilityMatrix[i] = r.NextDouble(); } Encoding.Length = data.Dimension; OnReset(); } }
• ## branches/PTSP/PTSP.sln

 r12166 MinimumVisualStudioVersion = 10.0.40219.1 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP-3.3", "HeuristicLab.Problems.PTSP\3.3\HeuristicLab.Problems.PTSP-3.3.csproj", "{97198965-AFEA-496B-B3B1-316905C43FD6}" EndProject Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Views-3.3", "HeuristicLab.Problems.PTSP.Views\3.3\HeuristicLab.Problems.PTSP.Views-3.3.csproj", "{90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}" EndProject Global {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.ActiveCfg = Release|Any CPU {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.Build.0 = Release|Any CPU {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.Build.0 = Debug|Any CPU {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution
Note: See TracChangeset for help on using the changeset viewer.