Travelling Salesman Problem (TSP) adalah salah satu permasalahan optimasi kombinatorial yang telah menantang para peneliti selama beberapa dekade. TSP melibatkan pencarian jalur terpendek yang melalui setiap titik (kota) tepat satu kali dan kembali ke titik awal. Algoritma optimasi yang populer digunakan untuk menyelesaikan TSP antara lain adalah Algoritma Genetika, Partikel Swarm Optimization (PSO), dan Tabu Search. Dalam artikel ini, kita akan mendalami tentang ketiga algoritma ini dan membandingkannya dalam konteks penyelesaian Travelling Salesman Problem.

1. Algoritma Genetika

Algoritma Genetika (AG) terinspirasi oleh mekanisme seleksi alamiah dan evolusi genetik. Pendekatan ini meniru proses seleksi alam dan reproduksi untuk menghasilkan solusi yang semakin baik dari generasi ke generasi. Proses evolusi pada AG melibatkan representasi solusi dalam bentuk kromosom, fungsi penilaian untuk mengukur kecocokan solusi, dan operasi genetik seperti seleksi, crossover, dan mutasi.

Dalam konteks TSP, solusi dapat diwakili sebagai urutan kota yang dikunjungi. AG menciptakan populasi awal solusi, kemudian menerapkan operator genetik seperti crossover untuk menggabungkan informasi dari dua solusi atau mutasi untuk memperkenalkan variasi. Proses ini diulang sejumlah generasi untuk mendapatkan solusi yang semakin baik.

Kelebihan AG meliputi kemampuannya menangani ruang pencarian besar, tetapi kekurangannya adalah ketergantungan pada parameter yang sulit ditentukan dan potensi untuk terjebak dalam solusi lokal optimum.

Baca Juga: Algoritma Genetika untuk Travelling Salesman Problem

2. Partikel Swarm Optimization (PSO)

PSO adalah algoritma optimasi yang terinspirasi oleh perilaku kawanan partikel dalam mencari makanan. Dalam PSO, solusi diwakili sebagai partikel yang bergerak dalam ruang pencarian. Setiap partikel memiliki posisi dan kecepatan yang berubah seiring waktu berdasarkan pengalaman pribadi dan pengalaman kawanan.

Dalam konteks TSP, setiap partikel merepresentasikan solusi yang mungkin. Partikel bergerak menuju solusi yang lebih baik dengan memperbarui posisi mereka berdasarkan pengalaman pribadi dan pengalaman yang diambil dari partikel tetangga. Proses ini dilakukan secara iteratif hingga konvergensi atau batasan iterasi tertentu tercapai.

Kelebihan PSO melibatkan kemampuannya untuk menjelajahi ruang pencarian dengan cepat, tetapi kekurangannya adalah ketergantungan pada parameter dan kecenderungan untuk terjebak dalam solusi lokal optimum.

Baca Juga: Penerapan Algoritma Particle Swarm Optimization (PSO) Pada Kasus Prediksi

3. Tabu Search

Tabu Search (TS) adalah algoritma optimasi yang bertujuan untuk mengatasi keterbatasan algoritma heuristik tradisional. TS menggunakan pendekatan intensifikasi dan diversifikasi dengan mempertahankan solusi yang lebih baik dan menghindari solusi yang telah dieksplorasi sebelumnya.

Dalam konteks TSP, TS mempertahankan solusi terbaik yang telah ditemukan dan mengimplementasikan aturan tabu untuk menghindari solusi yang serupa. Selama pencarian, TS menggunakan mekanisme diversifikasi untuk menjelajahi ruang pencarian dengan lebih baik dan meningkatkan kemungkinan menemukan solusi global optimum.

Kelebihan TS melibatkan kemampuannya untuk mengatasi solusi lokal optimum, tetapi kekurangannya termasuk ketergantungan pada parameter dan kinerja yang bisa bervariasi tergantung pada kondisi awal.

Perbandingan Ketiga Algoritma

1. Kinerja dan Kecepatan Konvergensi:

• AG cenderung memiliki konvergensi yang lebih lambat karena melibatkan proses evolusi generasi demi generasi.
• PSO memiliki kecepatan konvergensi yang cepat karena interaksi langsung antara partikel.
• TS memiliki kemampuan untuk mengatasi solusi lokal optimum, tetapi kecepatan konvergensinya dapat bervariasi.

1. Robustness dan Kemampuan Menangani Solusi Lokal Optimum:

• AG dan PSO memiliki kecenderungan untuk terjebak dalam solusi lokal optimum.
• TS terkenal karena kemampuannya menghindari solusi lokal optimum dan menjelajahi ruang pencarian lebih baik.

1. Kemampuan Menangani Ruang Pencarian Besar:

• AG dan PSO memiliki kemampuan menangani ruang pencarian besar karena sifatnya yang dapat diaplikasikan pada berbagai masalah.
• TS juga dapat menangani ruang pencarian besar, tetapi ketergantungan pada parameter dapat mempengaruhi kinerjanya.

1. Ketergantungan pada Parameter:

• AG, PSO, dan TS semuanya memiliki parameter yang perlu ditentukan dengan cermat.
• Sensitivitas terhadap parameter dapat memengaruhi kinerja dan konvergensi dari masing-masing algoritma.

1. Penerapan pada Travelling Salesman Problem:

• AG, PSO, dan TS semuanya telah berhasil diterapkan pada TSP dengan tingkat keberhasilan yang bervariasi.
• Pilihan algoritma tergantung pada karakteristik spesifik dari masalah TSP yang dihadapi.

Dalam perbandingan antara Algoritma Genetika, Partikel Swarm Optimization, dan Tabu Search dalam penyelesaian Travelling Salesman Problem, tidak ada satu algoritma yang benar-benar unggul dalam semua aspek. Pilihan antara ketiganya tergantung pada karakteristik masalah yang dihadapi, batasan sumber daya, dan preferensi pengguna. Oleh karena itu, pemilihan algoritma harus didasarkan pada pemahaman mendalam tentang sifat masalah dan kemampuan relatif dari masing-masing algoritma dalam menangani tantangan yang ada.

Berikut adalah implementasi dalam MATLAB untuk ketiga metode tersebut (Algoritma Genetika, Partikel Swarm Optimization, dan Tabu Search) untuk menyelesaikan Travelling Salesman Problem (TSP) dengan koordinat titik yang diberikan. Kode ini memberikan gambaran umum dan menggunakan representasi kromosom untuk solusi TSP.

Algoritma Genetika (AG) – MATLAB

function [bestPath, minLength] = geneticAlgorithm(X, Y, populationSize, generations)
    numCities = numel(X);
    population = initializePopulation(populationSize, numCities);

    for generation = 1:generations
        fitness = evaluateFitness(population, X, Y);
        selectedParents = selection(population, fitness);
        offspring = crossover(selectedParents);
        mutatedOffspring = mutation(offspring);
        combinedPopulation = [population; mutatedOffspring];
        newPopulation = elitismSelection(combinedPopulation, fitness, populationSize);
        population = newPopulation;
    end

    [minLength, index] = min(fitness);
    bestPath = population(index, :);
end

% Implementasikan fungsi-fungsi pendukung seperti initializePopulation, evaluateFitness,
% selection, crossover, mutation, dan elitismSelection sesuai kebutuhan.

Partikel Swarm Optimization (PSO) – MATLAB

function [bestPath, minLength] = particleSwarmOptimization(X, Y, swarmSize, iterations)
    numCities = numel(X);
    particles = initializeParticles(swarmSize, numCities);

    for iteration = 1:iterations
        fitness = evaluateFitness(particles, X, Y);
        particles = updateParticles(particles, fitness);
    end

    [minLength, index] = min(fitness);
    bestPath = particles(index, :);
end

% Implementasikan fungsi-fungsi pendukung seperti initializeParticles, evaluateFitness,
% dan updateParticles sesuai kebutuhan.

Tabu Search (TS) – MATLAB

function [bestPath, minLength] = tabuSearch(X, Y, tabuListSize, iterations)
    numCities = numel(X);
    currentSolution = initializeSolution(numCities);
    tabuList = zeros(tabuListSize, numel(currentSolution));

    for iteration = 1:iterations
        currentFitness = evaluateFitness(currentSolution, X, Y);
        neighborSolution = generateNeighborSolution(currentSolution);
        neighborFitness = evaluateFitness(neighborSolution, X, Y);
        [currentSolution, tabuList] = updateSolution(currentSolution, neighborSolution, currentFitness, neighborFitness, tabuList);
    end

    [minLength, index] = min(currentFitness);
    bestPath = currentSolution(index, :);
end

% Implementasikan fungsi-fungsi pendukung seperti initializeSolution, evaluateFitness,
% generateNeighborSolution, dan updateSolution sesuai kebutuhan.