{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Analisis Masalah\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Source Code, "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"import math\n",
"import random\n",
"import time\n",
"import pandas as pd\n",
"import csv\n",
"import sys\n",
"import datetime\n",
"import timeit"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"start = datetime.datetime.strptime(\"21-07-2020\", \"%d-%m-%Y\")\n",
"end = datetime.datetime.strptime(\"22-07-2020\", \"%d-%m-%Y\")\n",
"date_generated = [start + datetime.timedelta(days=x) for x in range(0, (end-start).days)]\n",
"#print(len(date_generated))"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"cost = 400000\n",
"Cost = int(cost)\n",
"min_cost = 399333"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"Weather = 26.897694"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"class Fitness_value:\n",
" def getting_max_distance():\n",
" max_distance = 0 \n",
" max_distance += len(date_generated) * 720\n",
" return max_distance\n",
" def getting_max_cost():\n",
" max_cost = 0\n",
" max_cost +=Cost\n",
" return max_cost"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"#Load dataset sebelum integrasi\n",
"#Datax = pd.read_csv('./Yolanda/tri/Data Toba Samosir_Sheet3.csv')\n",
"#Datax.drop(Datax.filter(regex=\"Unname\"),axis=1, inplace=True)\n",
"Datax = pd.read_csv('./Data Toba Samosir_Sheet3.csv')\n",
"Datax.drop(Datax.filter(regex=\"Unname\"),axis=1, inplace=True)\n",
"Dataz = pd.read_csv('./List_city.csv')\n",
"Dat = Datax.to_numpy()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0. , 50.9, 12.8, ..., 22.5, 14.4, 5.7],\n",
" [50.9, 0. , 59.2, ..., 32.9, 60.8, 52.1],\n",
" [12.8, 59.2, 0. , ..., 31.8, 4.5, 7.7],\n",
" ...,\n",
" [23.5, 32.9, 31.8, ..., 0. , 33.4, 24.7],\n",
" [14.4, 60.8, 4.5, ..., 33.4, 0. , 9.2],\n",
" [ 5.7, 52.1, 7.7, ..., 24.7, 9.2, 0. ]])"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Dat"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"#id_city = list(Dataz['ID_City'])\n",
"#path = random.sample(range(len(id_city)), 7)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"#Datax = pd.read_csv('./Yolanda/tri/Data Toba Samosir_Sheet1.csv')\n",
"#Datax.drop(Datax.filter(regex=\"Unname\"),axis=1, inplace=True)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def generate_start_nodes (individu,n_kota):\n",
" \"\"\"\n",
" :param individu:(int) jumlah semut\n",
" :param n_kota :(int) jumlah kota\n",
" :return : tabulist yang masih berisi start (dan end) node untuk semua individu semut\n",
" \"\"\"\n",
" start_nodes= []\n",
" for i in range (individu): \n",
" start_nodes.append([0 for i in range(n_kota+1)])\n",
" start_nodes[-1][0] = random.randint(0,(n_kota-1))\n",
" start_nodes[-1][-1] = start_nodes[-1][0]\n",
" return start_nodes"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"def evaluate_best_city (kota_sekarang, matriks_jarak ,tau, tabulist, alpha, beta):\n",
" \"\"\"\n",
" Mengevaluasi kota terbaik yang memungkinkan berdasarkan probabilitas dan tabulist\n",
" :param kota_sekarang: (int 0..15) \n",
" :param tabulist : (int[0..15]) merupakan kota yang sudah pernah dikunjungi oleh semut\n",
" :param tau : (list) intensitas pheromon pada \n",
" :param matriks_jarak: (matriks[16][16]) matriks yang berisi jarak antar kota\n",
" :return : kota dengan probabilitas tertinggi\n",
" \"\"\"\n",
" probability = [0] * np.size(matriks_jarak[1])\n",
" allowed = []\n",
" allowed[:] = [x for x in range(np.size(matriks_jarak[1])) if x not in tabulist]\n",
" p = 0\n",
" for i in allowed:\n",
" visibility = 1/matriks_jarak[kota_sekarang][i]\n",
" p += (tau[kota_sekarang][i]**alpha)*(visibility**beta)\n",
" for i in allowed:\n",
" visibility = 1/matriks_jarak[kota_sekarang][i]\n",
" probability[i] = (tau[kota_sekarang][i]**alpha)*(visibility**beta)/p\n",
" tmp = max(probability)\n",
" return probability.index(tmp)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def update_tau(individu, tau, tabulists, L, evaporation_coeff, Q,n_kota):\n",
" \"\"\"\n",
" :param evaporation: koefisien evaporation\n",
" :param tau : matriks tau seukuran kota x kota\n",
" :param L : matriks/array[1x16] yang mengandung informasi jarak tour yang\n",
" dihasilkan oleh satu semut\n",
" :param delta_tau : matriks seukuran kota x kota\n",
" :return : tau yang baru\n",
" \"\"\"\n",
" for i in range (individu):\n",
" for j in range (n_kota):\n",
" delta_tau = Q/L[i]\n",
" tau[tabulists[i][j],tabulists[i][j+1]] = evaporation_coeff * tau[tabulists[i][j],tabulists[i][j+1]] + delta_tau\n",
" return (tau)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def hitung_jarak_1_rute(single_solution,matriks_jarak):\n",
" \"\"\"\n",
" :param single_solution: Sebuah tabulist dari seekor semut (1 solusi) [0..16]\n",
" :param matriks_jarak : matriks jarak antar node\n",
" :return : Total jarak yang dihasilkan solusi tersebut\n",
" \"\"\"\n",
" jarak = 0\n",
" for i in range (len(single_solution)-1):\n",
" jarak += matriks_jarak[single_solution[i]][single_solution[i+1]] \n",
" return (jarak)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"def compute_shortest_distances(tabulists, matriks_jarak):\n",
" \"\"\"\n",
" :param tabulists: Tabulist sejumlah individu x banyak kota\n",
" :return : tuple (jarak terkecil yang di temukan (float)\n",
" rute dengan jarak terkecil (list),\n",
" list jarak (L)(list)\n",
" rata2 jarak yang ditemukan (float))\n",
" :>>>(min_dist,route,L,rerata)\n",
" \"\"\"\n",
" distances = []\n",
" distances = [0] * len(tabulists)\n",
" for i in range(0,len(tabulists)):\n",
" distances[i] = hitung_jarak_1_rute(tabulists[i],matriks_jarak)\n",
" L = distances\n",
" L = L- 0.97*min(L)\n",
" return (min(distances) , tabulists[distances.index(min(distances))] , L, np.mean(distances))"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"#tabulists"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"Maximum_distance = Fitness_value.getting_max_distance()\n",
"Maximum_cost = Fitness_value.getting_max_cost()\n",
"TARGET_weather = Weather\n",
"CITY_COUNT = len(Datax)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"400000"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Maximum_cost"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Route : [4, 23, 31, 14, 32, 4]\n",
"27.43 , 399333 , 26.897694\n",
"\n",
"\n",
"Route : [4, 31, 23, 32, 15, 4]\n",
"45.42999999999999 , 399333 , 26.897694\n",
"\n",
"\n",
"Route : [2, 35, 14, 20, 16, 2]\n",
"25.150000000000002 , 399333 , 26.897694\n",
"\n",
"\n",
"Route : [2, 35, 23, 31, 15, 2]\n",
"22.730000000000004 , 399333 , 26.897694\n",
"\n",
"\n",
"Route : [2, 16, 24, 18, 7, 2]\n",
"59.3 , 399333 , 26.897694\n",
"\n",
"\n"
]
}
],
"source": [
"running = 5\n",
"global_distance = []\n",
"\n",
"for run in range (running):\n",
" iterasi = 50\n",
" alpha = 2 #jejak pheromon\n",
" beta = 2#visibility\n",
" individu = 40\n",
" n_kota = 5\n",
" evaporation_coeff = 0.1\n",
" Q = 1\n",
" nodelist = []\n",
"\n",
" matriks_jarak = Dat\n",
" tau = np.ones(np.shape(matriks_jarak))*0.5 #init. intensitas pheromon/jejak pada busur\n",
" delta_tau = np.zeros((n_kota,n_kota))\n",
"\n",
" shortest_distance = math.inf #infinit\n",
"\n",
" shortest_route = []\n",
" average = []\n",
" for i in range (iterasi):\n",
" tabulists = generate_start_nodes(individu,n_kota)\n",
" for j in range (1,n_kota):\n",
" for k in range (individu):\n",
" tabulists[k][j] = evaluate_best_city(tabulists[k][j-1],matriks_jarak,tau, tabulists[k],alpha,beta)\n",
" min_dist,route,L,rerata = compute_shortest_distances(tabulists,matriks_jarak)\n",
" average.append(rerata)\n",
"\n",
" if ((shortest_distance > min_dist) and (shortest_distance > Maximum_distance) and (min_cost <=Maximum_cost) and ((Weather >=18) and (Weather <=28))):\n",
" shortest_distance = min_dist\n",
" shortest_route = route\n",
"\n",
" tau = update_tau(individu, tau, tabulists, L, evaporation_coeff, Q,n_kota)\n",
"\n",
" print (\"Route : \",route)\n",
" print (min_dist,\",\",min_cost,\",\",Weather)\n",
" global_distance.append(shortest_distance)\n",
" print(\"\\n\")\n",
"\n",
"#for shortest in global_distance:\n",
"# print (shortest) \n",
"\n",
"\n",
"#print (\"Rata-rata rute terpendek yang dihasilkan: \",np.average(global_distance))\n"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 16, 24, 18, 7, 2]"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"route"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#route = []"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [],
"source": [
"def decoding_ACO():\n",
" name = 0\n",
" for i in range(len(route)):\n",
" name = route[i]\n",
" print(Dataz.iloc[name][1])\n",
" i+=1\n",
" return "
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Pakkodian\n",
"Pantai Meat\n",
"Dolok Tolong\n",
"Air Terjun Siboruon\n",
"Air Terjun Pandumaan\n",
"Pakkodian\n"
]
}
],
"source": [
"decoding_ACO()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}