nsga2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ZIsR_g-hFA7k"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "import random\n",
    "from random import shuffle\n",
    "import matplotlib.pyplot as plt\n",
    "from cvxopt import matrix as cvxopt_matrix\n",
    "from cvxopt import solvers as cvxopt_solvers\n",
    "cvxopt_solvers.options['show_progress'] = False\n",
    "\n",
    "#Polynomial Kernel\n",
    "def kernel(x, y, order):\n",
    "    return (1 + np.dot(x, y)) ** order\n",
    "\n",
    "#Training Function\n",
    "def train(X, y, classes, C, order):\n",
    "  m,n = X.shape\n",
    "  params = {}\n",
    "\n",
    "  #Kernel Matrix\n",
    "  H = np.zeros((m,m))\n",
    "  for i in range(m):\n",
    "    for j in range(m):\n",
    "      H[i,j] = kernel(X[i],X[j],order)\n",
    "  #print(\"H Matrix done\")\n",
    "  \n",
    "  for i in range(classes):\n",
    "    #CVXOPT Initialization\n",
    "    yc = y/(i+1)\n",
    "    yc[yc != 1] = -1\n",
    "    #print(yc[:200])\n",
    "    P = cvxopt_matrix(np.outer(yc,yc) * H)\n",
    "    q = cvxopt_matrix(-np.ones((m, 1)))\n",
    "    G = cvxopt_matrix(np.vstack((np.eye(m)*-1,np.eye(m))))\n",
    "    h = cvxopt_matrix(np.hstack((np.zeros(m), np.ones(m) * C)))\n",
    "    A = cvxopt_matrix(yc.reshape(1, -1))\n",
    "    b = cvxopt_matrix(np.zeros(1))\n",
    "\n",
    "    #Run Solver\n",
    "    svm_h = cvxopt_solvers.qp(P, q, G, h, A, b)\n",
    "    alphas = np.ravel(svm_h['x'])\n",
    "\n",
    "    #All SVs\n",
    "    S = (alphas > 1e-9)\n",
    "    y_sv = yc[S]\n",
    "    alphas_sv = alphas[S]\n",
    "    X_sv = X[S]\n",
    "    #print(len(alphas_sv))\n",
    "\n",
    "    #Marginal SVs\n",
    "    T = ((alphas > 1e-9) &(alphas < (C-1e-4)))\n",
    "    y_msv = yc[T]\n",
    "    alphas_msv = alphas[T]\n",
    "    X_msv = X[T]\n",
    "    #print(len(alphas_msv))\n",
    "\n",
    "    #bias calculation\n",
    "    b = 0\n",
    "    for a in range(len(alphas_msv)):\n",
    "      sum = 0\n",
    "      for s in range(len(alphas_sv)):\n",
    "        sum = sum + alphas_sv[s] * y_sv[s] * kernel(X_msv[a],X_sv[s],order)\n",
    "      b = b + y_msv[a] - sum\n",
    "    b = b/len(alphas_msv)\n",
    "\n",
    "    #Parameters for class i+1\n",
    "    params['alphas_sv' + str(i+1)] = alphas_sv\n",
    "    params['X_sv' + str(i+1)] = X_sv\n",
    "    params['y_sv' + str(i+1)] = y_sv\n",
    "    params['b' + str(i+1)] = b\n",
    "\n",
    "    #print(\"Number of Classes Completed:\", i+1)\n",
    "\n",
    "  return(params)\n",
    "\n",
    "#Prediction Function\n",
    "def predict(X, params, classes, order):\n",
    "  score_set = np.zeros((classes)) #\n",
    "\n",
    "  for i in range(classes):\n",
    "    alphas_sv = params['alphas_sv' + str(i+1)]\n",
    "    X_sv = params['X_sv' + str(i+1)]\n",
    "    y_sv = params['y_sv' + str(i+1)]\n",
    "    b = params['b' + str(i+1)]\n",
    "\n",
    "    sum = 0\n",
    "    for s in range(len(alphas_sv)):\n",
    "      sum += alphas_sv[s] * y_sv[s] * kernel(X, X_sv[s],order)\n",
    "    sum += b\n",
    "    score_set[i] = sum\n",
    "\n",
    "  prediction = np.argmax(score_set) + 1.\n",
    "  return(prediction)\n",
    "\n",
    "#Train Set\n",
    "X_train1 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/X_train.npy')\n",
    "Y_train1 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/Y_train.npy')\n",
    "index = [i for i in range(len(X_train1))]\n",
    "shuffle(index)\n",
    "X_train1 = X_train1[index]\n",
    "Y_train1 = Y_train1[index]\n",
    "Y_train1 = Y_train1 + 1\n",
    "\n",
    "#Test Set 2\n",
    "X_test2 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/X_test2.npy')\n",
    "Y_test2 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/Y_test2.npy')\n",
    "index = [i for i in range(len(X_test2))]\n",
    "shuffle(index)\n",
    "X_test2 = X_test2[index]\n",
    "Y_test2 = Y_test2[index]\n",
    "Y_test2 = Y_test2 + 1\n",
    "\n",
    "#Test Set 1\n",
    "X_test1 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/X_test.npy')\n",
    "Y_test1 = np.load('/content/drive/My Drive/Colab Notebooks/8 class SVM/Y_test.npy')\n",
    "Y_test1  = Y_test1 + 1\n",
    "\n",
    "#Final Training and Testing Data\n",
    "X_train = np.vstack((X_train1[:200],X_test2[:200]))\n",
    "Y_train = np.hstack((Y_train1[:200],Y_test2[:200]))\n",
    "\n",
    "X_test = np.vstack((X_test1,X_test2))\n",
    "Y_test = np.hstack((Y_test1,Y_test2))\n",
    "\n",
    "#Target Function\n",
    "def functionopt(C, order, classes = 8, X = X_train, Y = Y_train, X_test = X_test, Y_test = Y_test):\n",
    "  #Training\n",
    "  parameters = train(X,Y,classes,C,order)\n",
    "\n",
    "  #Prediction\n",
    "  y_predict = np.zeros(len(X_test))\n",
    "  for i in range(len(X_test)):\n",
    "    y_predict[i] = predict(X_test[i],parameters,classes,order)\n",
    "  \n",
    "  correct = np.sum(y_predict == Y_test)\n",
    "  Accuracy = (correct)/len(y_predict)\n",
    "\n",
    "  #Recall of Class 1\n",
    "  check = (Y_test == 1)\n",
    "  y_predict_1 = y_predict[check]\n",
    "  Recall = np.sum(y_predict_1 == 1)/len(y_predict_1)\n",
    "  return Accuracy,Recall\n",
    "\n",
    "#Function to find index of a list\n",
    "def index_search(a,list):\n",
    "    for i in range(len(list)):\n",
    "        if list[i] == a:\n",
    "            return i\n",
    "    return -1\n",
    "\n",
    "#Function to sort by values\n",
    "def sort_by_values(list, values):\n",
    "    sorted_list = []\n",
    "    while(len(sorted_list)!=len(list)):\n",
    "        if index_search(min(values),values) in list:\n",
    "            sorted_list.append(index_search(min(values),values))\n",
    "        values[index_search(min(values),values)] = math.inf\n",
    "    return sorted_list\n",
    "\n",
    "#NSGA-2 non dominated sort\n",
    "def non_dominated_sort(values1, values2):\n",
    "    S=[[] for i in range(len(values1))]\n",
    "    front = [[]]\n",
    "    n=[0 for i in range(len(values1))]\n",
    "\n",
    "    for p in range(len(values1)):\n",
    "        for q in range(len(values1)):\n",
    "            if (values1[p] > values1[q] and values2[p] > values2[q]) or (values1[p] >= values1[q] and values2[p] > values2[q]) or (values1[p] > values1[q] and values2[p] >= values2[q]):\n",
    "                if q not in S[p]:\n",
    "                    S[p].append(q)\n",
    "            elif (values1[q] > values1[p] and values2[q] > values2[p]) or (values1[q] >= values1[p] and values2[q] > values2[p]) or (values1[q] > values1[p] and values2[q] >= values2[p]):\n",
    "                n[p] = n[p] + 1\n",
    "        if n[p]==0:\n",
    "            if p not in front[0]:\n",
    "                front[0].append(p)\n",
    "    \n",
    "    i = 0\n",
    "    while(front[i] != []):\n",
    "        Q=[]\n",
    "        for p in front[i]:\n",
    "            for q in S[p]:\n",
    "                n[q] =n[q] - 1\n",
    "                if( n[q]==0):\n",
    "                    if q not in Q:\n",
    "                        Q.append(q)\n",
    "        i = i+1\n",
    "        front.append(Q)\n",
    "    del front[len(front)-1]\n",
    "    return front\n",
    "\n",
    "#Crowding distance\n",
    "def crowding_distance(values1, values2, front):\n",
    "    distance = [0 for i in range(len(front))]\n",
    "    sorted1 = sort_by_values(front, values1[:])\n",
    "    sorted2 = sort_by_values(front, values2[:])\n",
    "    #print(values2)\n",
    "    for i in range(len(front)):\n",
    "      if (front[i] == sorted1[0]) or (front[i] == sorted2[0]) or (front[i] == sorted1[-1]) or (front[i] == sorted2[-1]):\n",
    "        distance[i] = 1000\n",
    "      else:\n",
    "        distance[i] += (values1[sorted1[index_search(front[i],sorted1)+1]] - values1[sorted1[index_search(front[i],sorted1)-1]])/(max(values1)-min(values1))\n",
    "        distance[i] += (values2[sorted2[index_search(front[i],sorted2)+1]] - values2[sorted2[index_search(front[i],sorted2)-1]])/(max(values2)-min(values2))\n",
    "    return distance\n",
    "\n",
    "#Function to carry out the crossover\n",
    "def crossover(a,b):\n",
    "    offspring = []\n",
    "    #Crossover for C\n",
    "    r = random.random()\n",
    "    if r>0.4:\n",
    "      offspring.append((a[0]+b[0])/2)\n",
    "    else:\n",
    "      offspring.append(mutation(a[0],b[0]))\n",
    "    #Crossover for order\n",
    "    r = random.random() \n",
    "    if r>0.5:\n",
    "        offspring.append(a[1])\n",
    "    else:\n",
    "        offspring.append(b[1])\n",
    "    return offspring\n",
    "\n",
    "#Mutation for C\n",
    "def mutation(a,b):\n",
    "  mutatedC = ((a+b)/2) * (random.random()) * 2\n",
    "  if mutatedC > 1:\n",
    "    return mutatedC\n",
    "  else:\n",
    "    return 1\n",
    "\n",
    "#Initilisation of first generation\n",
    "C = [5.0,15.0,25.0,35.0,45.0,55.0,65.0,75.0]\n",
    "order = [2,3,4]\n",
    "pop_size = len(C)*len(order)\n",
    "Pop = []\n",
    "for i in order:\n",
    "  for j in C:\n",
    "    Pop.append([j,i]) #Each Pair: [C,order]\n",
    "\n",
    "Full_Pop = Pop[:] #Full_Pop includes offspring of Pop\n",
    "for i in range(pop_size):\n",
    "  offspring = crossover(Pop[pop_size-i-2],Pop[pop_size-i-1])\n",
    "  if offspring not in Full_Pop:\n",
    "    Full_Pop.append(offspring)\n",
    "\n",
    "while len(Full_Pop) != 2*pop_size: #To complete first population\n",
    "  offspring = crossover(Full_Pop[random.randint(0,len(Full_Pop)-1)],Full_Pop[random.randint(0,len(Full_Pop)-1)])\n",
    "  if offspring not in Full_Pop:\n",
    "    Full_Pop.append(offspring)\n",
    "#print(Full_Pop)\n",
    "\n",
    "#Main Loop\n",
    "max_generations = 4\n",
    "gen_count = 0\n",
    "while gen_count < max_generations:\n",
    "  #Optimization Metric Calculation\n",
    "  Accuracy_values = []\n",
    "  Recall_values = []\n",
    "  for i in range(len(Full_Pop)):\n",
    "    A,R = functionopt(Full_Pop[i][0], Full_Pop[i][1])\n",
    "    Accuracy_values.append(A)\n",
    "    Recall_values.append(R)\n",
    "  \n",
    "  #Obtaining Fronts using Optimization Metrics\n",
    "  non_dominated_sorted_fronts = non_dominated_sort(Accuracy_values[:],Recall_values[:])\n",
    "  #print(non_dominated_sorted_fronts)\n",
    "  \n",
    "  #Calculation of Crowding Distance\n",
    "  crowding_distance_values=[]\n",
    "  for i in range(len(non_dominated_sorted_fronts)):\n",
    "    crowding_distance_values.append(crowding_distance(Accuracy_values[:],Recall_values[:],non_dominated_sorted_fronts[i][:]))\n",
    "  #print(crowding_distance_values)\n",
    "\n",
    "  gen_count += 1\n",
    "  print(\"The best pairs of Generation\",gen_count,\"are\")\n",
    "  for pair in non_dominated_sorted_fronts[0]:\n",
    "      print(Full_Pop[pair], \", with Accuracy\",Accuracy_values[pair]*100,\"%, with Recall for Class-1\",Recall_values[pair]*100,\"%\")\n",
    "  print(\"\\n\")\n",
    "\n",
    "  #Creating New Population\n",
    "  new_Poplist = []  #List of pairs to be taken from previous generation\n",
    "  for i in range(len(non_dominated_sorted_fronts)):\n",
    "    front_i_index = [j for j in range(len(non_dominated_sorted_fronts[i]))]   #List of indices of the pairs in each front\n",
    "    dist_sorted_front_i_index = sort_by_values(front_i_index[:], crowding_distance_values[i][:])    #Sorting above list using Crowding Distance of that front\n",
    "    front_ascending_distance = [non_dominated_sorted_fronts[i][dist_sorted_front_i_index[j]] for j in range(len(non_dominated_sorted_fronts[i]))]    \n",
    "    front_ascending_distance.reverse()\n",
    "    front_descending_distance = front_ascending_distance[:] #List of pairs from previous generation within each front arranged in descending order w.r.t. Crowding Distance\n",
    "    for pair_number in front_descending_distance:\n",
    "      new_Poplist.append(pair_number)\n",
    "      if (len(new_Poplist)==pop_size):\n",
    "        break\n",
    "    if (len(new_Poplist) == pop_size): #We only take best half of previous generation\n",
    "      break\n",
    "\n",
    "  Pop = [Full_Pop[i] for i in new_Poplist]  \n",
    "  Full_Pop = Pop[:] #Full_Pop2 contains new Pop and it's offspring\n",
    "  for i in range(math.ceil(pop_size/2)):\n",
    "    offspring = crossover(Pop[random.randint(0,math.ceil(len(Pop)/2))],Pop[random.randint(0,math.ceil(len(Pop)/2))])\n",
    "    if offspring not in Full_Pop:\n",
    "      Full_Pop.append(offspring)\n",
    "\n",
    "  while len(Full_Pop) != 2*pop_size: #To complete population\n",
    "    offspring = crossover(Full_Pop[random.randint(0,len(Full_Pop)-1)],Full_Pop[random.randint(0,len(Full_Pop)-1)])\n",
    "    if offspring not in Full_Pop:\n",
    "      Full_Pop.append(offspring)\n",
    "  #print(Full_Pop)\n",
    "\n",
    "#Final Population\n",
    "print(\"The Final Population is:\")\n",
    "print(Pop)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "nsga2.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}