Studi Komparatif: Pembentukan Dataset & Perbandingan Algoritma

"Penelitian yang kuat membutuhkan data yang kredibel dan terstandardisasi. Dataset yang ideal adalah fondasi dari eksperimen yang dapat dipercaya dan direplikasi."

1️⃣ Metodologi Pembentukan Dataset Ideal

📌 Struktur Dataset Berdasarkan Graf Lengkap

Dataset yang digunakan dirancang secara sistematis sebagai koleksi graf lengkap tidak berarah. Untuk setiap ukuran simpul (n), dibentuk 30 instance graf yang masing-masing merepresentasikan sebuah graf lengkap dengan bobot sisi (edge) yang dihasilkan melalui distribusi acak terkontrol. Dataset disimpan dalam format tabular ('.csv'), di mana setiap kolom adalah satu instance graf.

Jumlah sisi (edge) untuk setiap graf lengkap dihitung menggunakan rumus kombinasi dua simpul, E = (n(n - 1))/2.


CONTOH DATASET NORM
https://drive.google.com/drive/folders/17drXA4T3gxwuRGxrZgKOkAeZS9Cml1Gx?usp=sharing

2️⃣ Analisis & Perbandingan Dataset

💡 Kelemahan Dataset Acak pada Umumnya

Analisis terhadap dataset acak menunjukkan beberapa keterbatasan signifikan yang berpotensi memengaruhi validitas eksperimen:

✅ Karakteristik Dataset Ideal

Untuk mengatasi masalah tersebut, dataset ideal dirancang dengan pendekatan statistik yang terkontrol, didukung oleh tiga karakteristik utama:

  1. Distribusi Normal: Bobot sisi dibangkitkan menggunakan distribusi normal (Gaussian) untuk menciptakan penyebaran nilai yang simetris dan menghindari nilai ekstrem.
  2. Rentang Terkontrol: Nilai bobot dibatasi dengan rentang minimum dan maksimum yang proporsional dengan ukuran graf, menghindari anomali data.
  3. Konsistensi Antar Kolom: Setiap instance graf memiliki karakteristik statistik yang seragam, memastikan kondisi pengujian yang adil.

3️⃣ Implementasi dan Parameter Pembangkitan Data

Proses pembentukan dataset ideal diimplementasikan menggunakan Python, dengan pustaka seperti 'numpy' dan 'pandas'.

Parameter Distribusi Bobot:

Ukuran Vertex Mean (μ) Std Dev (σ) Min Weight Max Weight
10–50 50 10 10 100
60–100 100 20 20 200
150–300 200 40 50 400
350–500 300 60 100 500

Penggunaan parameter ini memastikan dataset dapat direproduksi dan konsisten secara statistik, mendukung validitas eksperimen.

Analisis Perbandingan Algoritma ACO

Analisis Perbandingan Algoritma ACO

"Kekuatan sebuah algoritma heuristik terukur dari seberapa dekat ia dapat meniru solusi optimal yang ditemukan oleh metode pasti, di bawah berbagai kondisi yang menantang."

1️⃣ Ringkasan Hasil Eksperimen

Perbandingan Kinerja pada Dataset Acak & Normal

Eksperimen ini membandingkan kinerja berbagai varian Algoritma ACO (Ant Colony Optimization) terhadap solusi optimal yang ditemukan oleh Algoritma Kruskal. Pengujian dilakukan pada dua jenis dataset: Dataset Acak (acak, tidak terkontrol) dan Dataset Normal (ideal, terdistribusi normal).

Ukuran Vertex Metode Uji Gap dari Optimal (Acak) Gap dari Optimal (Normal)
10 ACO TSP Path vs Kruskal +23.41% +4.31%
ACO MST vs Kruskal +0.00% +0.04%
20 ACO TSP Path vs Kruskal +45.33% +9.70%
ACO MST vs Kruskal +0.09% +0.44%
30 ACO TSP Path vs Kruskal +69.48% +14.58%
ACO MST vs Kruskal +0.02% +0.78%
40 ACO TSP Path vs Kruskal +75.69% +14.02%
ACO MST vs Kruskal +0.19% +1.17%
50 ACO TSP Path vs Kruskal +81.67% +17.55%
ACO MST vs Kruskal +0.18% +1.54%
60 ACO TSP Path vs Kruskal +94.05% +19.56%
ACO MST vs Kruskal +0.19% +1.60%
70 ACO TSP Path vs Kruskal +99.41% +20.00%
ACO MST vs Kruskal +0.25% +2.09%
80 ACO TSP Path vs Kruskal +104.16% +4.31%
ACO MST vs Kruskal +0.36% +0.04%
90 ACO TSP Path vs Kruskal +110.80% +23.18%
ACO MST vs Kruskal +0.45% +2.26%
100 ACO TSP Path vs Kruskal +118.10% +24.27%
ACO MST vs Kruskal +0.42% +2.51%

2️⃣ Opini dan Kesimpulan

✅ Performa Superior ACO untuk Masalah MST

💡 Dampak Besar Kualitas Dataset

🔬 Implikasi Terhadap Desain Algoritma