Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Lab 4 Report

    Uploaded by

    Woods Four
    The document presents an analysis of using an evolutionary method in Microsoft Excel to solve the traveling salesman problem (TSP). Three sets of parameter settings were tested with population sizes of 100, 200, and 300. The average tour length decreased while the optimal tour length remained constant as the population size increased, indicating better exploration of solutions. The deviation percentage, which measures the difference between average and optimal tour lengths, also decreased with larger population sizes, showing improved convergence. Therefore, the evolutionary method provided efficient and reliable solutions to the complex TSP optimization problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lab 4 Report

    Uploaded by

    Woods Four
    31 views5 pages
    The document presents an analysis of using an evolutionary method in Microsoft Excel to solve the traveling salesman problem (TSP). Three sets of parameter settings were tested with population sizes of 100, 200, and 300. The average tour length decreased while the optimal tour length remained constant as the population size increased, indicating better exploration of solutions. The deviation percentage, which measures the difference between average and optimal tour lengths, also decreased with larger population sizes, showing improved convergence. Therefore, the evolutionary method provided efficient and reliable solutions to the complex TSP optimization problem.

    Original Title

    Lab_4_Report

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document presents an analysis of using an evolutionary method in Microsoft Excel to solve the traveling salesman problem (TSP). Three sets of parameter settings were tested with population sizes of 100, 200, and 300. The average tour length decreased while the optimal tour length remained constant as the population size increased, indicating better exploration of solutions. The deviation percentage, which measures the difference between average and optimal tour lengths, also decreased with larger population sizes, showing improved convergence. Therefore, the evolutionary method provided efficient and reliable solutions to the complex TSP optimization problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views5 pages

    Lab 4 Report

    Uploaded by

    Woods Four
    The document presents an analysis of using an evolutionary method in Microsoft Excel to solve the traveling salesman problem (TSP). Three sets of parameter settings were tested with population sizes of 100, 200, and 300. The average tour length decreased while the optimal tour length remained constant as the population size increased, indicating better exploration of solutions. The deviation percentage, which measures the difference between average and optimal tour lengths, also decreased with larger population sizes, showing improved convergence. Therefore, the evolutionary method provided efficient and reliable solutions to the complex TSP optimization problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 5

    INDIVIDUAL LAB REPORT 4

    (TRAVELING SALESMAN PROBLEM)

    CMM426
    BUSINESS INTELLIGENCE AND ANALYTICS

    SEMESTER 2
    ACADEMIC SESSION 2022/2023

    PREPARED BY: LIM LIEW XING


    MATRIC NO: 152032
    TABLE OF CONTENTS

    Part 1: A spreadsheet model for swiss42.................................................................................... 1


    Part 2: Detailed parameter settings with corresponding results ................................................. 1
    Set 1 ........................................................................................................................................ 1
    Set 2 ........................................................................................................................................ 1
    Set 3 ........................................................................................................................................ 2
    Result in Tabular Format ........................................................................................................ 3

    ii
    Part 1: A spreadsheet model for swiss42

    The spreadsheet model can be found in the zip file named “swiss42.csv”. There are three sets

    of different parameters setting with five times of running.

    Part 2: Detailed parameter settings with corresponding results.

    Set 1:

    Convergence = 0.0001
    Mutation rate = 0.075
    Population size = 100
    Random seed = 0
    Maximum time without improvement = 30s
    Require Bounds on Variables

    Run 1: 1371
    Run 2: 1317
    Run 3: 1375
    Run 4: 1305
    Run 5: 1354

    Average Tour Length: (1371 + 1317 + 1375 + 1305 + 1354) / 5 = 1344.4


    Optimal Tour Length: 1273
    Deviation percentage: (1344.4– 1273) / 1273 * 100% = 5.61%

    Set 2:

    Convergence = 0.0001
    Mutation rate = 0.075
    Population size = 200
    Random seed = 0
    Maximum time without improvement = 30s
    Require Bounds on Variables

    1
    Run 1: 1367
    Run 2: 1366
    Run 3: 1412
    Run 4: 1381
    Run 5: 1341

    Average Tour Length: (1367 + 1366 + 1412 + 1381 + 1341) / 5 =1373.4


    Optimal Tour Length: 1273
    Deviation percentage: (1373.4– 1273) / 1273 * 100% = 7.89%

    Set 3:

    Convergence = 0.0001
    Mutation rate = 0.075
    Population size = 300
    Random seed = 0
    Maximum time without improvement = 30s
    Require Bounds on Variables

    Run 1: 1376
    Run 2: 1465
    Run 3: 1386
    Run 4: 1409
    Run 5: 1398

    Average Tour Length: (1376 + 1465 + 1386 + 1409 + 1398) / 5 = 1406.8


    Optimal Tour Length: 1273
    Deviation percentage: (1406.8– 1273) / 1273 * 100% = 10.51%

    2
    Result in Tabular Format

    Set Population Average Tour Optimal Tour Length Deviation


    Size Length percentage (%)
    1 100 1344.4 1273 5.61%

    2 200 1373.4 1273 7.89%

    3 300 1406.8 1273 10.51%

    The presented analysis showcases the performance of the Evolutionary Method


    implemented in Microsoft Excel Solver for solving the Traveling Salesman Problem (TSP). The
    Evolutionary Method, a metaheuristic algorithm inspired by natural evolution, aims to find
    optimal solutions. In this case, the TSP involves determining the shortest route for a traveling
    salesman to visit a set of cities and return to the starting city, minimizing the total distance traveled
    (tour length).The average tour length, representing the average distance covered by the salesman
    across multiple algorithm iterations, was observed to decrease as the population size increased.
    This trend suggests that a larger population size enables better exploration and exploitation of the
    solution space, leading to improved solutions. The optimal tour length, which corresponds to the
    best solution found by the algorithm (i.e., the shortest tour length achieved), remained constant
    for different population sizes. This consistency indicates that the Evolutionary Method converged
    to the same optimal solution in each case.

    The deviation percentage provides insight into the difference between the average tour
    length and the optimal tour length, expressed as a percentage. For a population size of 100, the
    deviation percentage was calculated to be 5.61%. With a population size of 200, the deviation
    percentage increased to 7.89%, and for a population size of 300, the deviation percentage further
    rose to 10.51%. A lower deviation percentage signifies a closer alignment between the average
    tour length and the optimal tour length, indicating better convergence and solution quality. Based
    on these findings, it is evident that the Evolutionary Method, implemented using Microsoft Excel
    Solver, effectively addresses the Traveling Salesman Problem. The algorithm's ability to find
    near-optimal solutions, as indicated by the decreasing deviation percentage with larger population
    sizes, demonstrates its efficiency and reliability in solving this complex optimization problem.

    You might also like