Genetic_Algorithm.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.8.6"
    },
    "colab": {
      "name": "Genetic Algorithm.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ayush5harma/ViewshedAnalysis/blob/master/Genetic_Algorithm.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cQIFH0uKzH0e"
      },
      "source": [
        "\n",
        "import numpy as np\n",
        "import random\n",
        "from bresenham import bresenham\n",
        "import csv\n",
        "import subprocess, pandas as pd\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import os"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yfMjx7XGzH0g"
      },
      "source": [
        "fn = 'DEM_30m_whole_area.tif'\n",
        "\n",
        "from numpy import load\n",
        "\n",
        "rasterArray = np.array(load('dem.npy'))\n",
        "#dem.npy file and buffer are needed for running this code\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1PW2M1tpzH0h"
      },
      "source": [
        "size_x=rasterArray.shape[0]\n",
        "size_y=rasterArray.shape[1]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zoGPNQDMzH0i"
      },
      "source": [
        "def switch(k):\n",
        "    ps = {\n",
        "        1: 'CPU-R2-',\n",
        "        2: 'GPU-R2-',\n",
        "        3: 'CPU-R3-',\n",
        "        4: 'GPU-R3-'\n",
        "    }\n",
        "    return ps.get(k, 'Invalid Choice')\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kQgwq8KuzH0i"
      },
      "source": [
        "def viewshed_gpu(Visiblity, obs_X, obs_Y, path, radius, dem_x, dem_y, type):\n",
        "    inp = path + '\\n' + str(dem_x) + '\\n' + str(dem_y) + '\\n' + str(radius) + '\\n' + str(obs_X) + '\\n' + str(obs_Y) + '\\n' + str(type) + '\\n'\n",
        "    res = bytes(inp, 'utf-8')\n",
        "    process = subprocess.Popen(\"Release/RasterViewshed.exe\", stdin=subprocess.PIPE, stdout=subprocess.PIPE)\n",
        "    std = process.communicate(input=res)[0]\n",
        "    ps = switch(type)\n",
        "    pa = ps + str(obs_X) + '-' + str(obs_Y) + '.csv'\n",
        "    pa1 = ps + str(obs_X) + '-' + str(obs_Y) + '.bmp'\n",
        "    pk='1sat'+ str(obs_X) + '-' + str(obs_Y) + '.csv'\n",
        "    df = pd.DataFrame()\n",
        "    view = np.genfromtxt(pa, delimiter=\",\")\n",
        "    view = view[:, :-1]\n",
        "    for i in range(size_x):\n",
        "        for j in range(size_y):\n",
        "            if view[i, j]==1:\n",
        "                d={\n",
        "                    'x':i,\n",
        "                    'y':j\n",
        "                }\n",
        "                df=df.append(d,ignore_index=True)\n",
        "    \n",
        "    df.to_csv(pk)\n",
        "    \n",
        "    for d in df.index:\n",
        "        x=int(df['x'][d])\n",
        "        y=int(df['y'][d])\n",
        "        Visiblity[int(x),int(y)]=1\n",
        "    os.remove(pa1)\n",
        "    os.remove(pa)\n",
        "    return Visiblity"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_DK5k3TMzH0j"
      },
      "source": [
        "ridgeline_buffer=np.load(\"Buffer\")\n",
        "ridgeline_buffer=ridgeline_buffer.tolist()  #here bufferridgeline_buffer refers to the Ridgeline-buffer obtained by running the ridgeline-buffer code first. The values once obtained can be saved as a spydata file for future use.\n",
        "no_of_ridgeline_points = len(ridgeline_buffer)\n",
        "\n",
        "no_of_iterations = int(input(\"enter the number of iterations\"))\n",
        "\n",
        "no_of_particles = int(input(\"enter the number of particles\"))  #no. of chromosomes to be initialized in the population\n",
        "\n",
        "no_of_viewpoints = int(input(\"enter the number of viewpoints\"))\n",
        "\n",
        "radius = int(input(\"enter the radius of coverage by viewpoints\"))  #Should be given in terms of pixels. Example:- radius = 500 means radius of 500 pixels which equals 500*30 = 15km approx.\n",
        "\n",
        "crossover_rate = float(input(\"enter the crossover rate\"))   #a Floating point value between 0 and 1. Example:- 0.8 means the new generation would have 80% new chromosomes obtained by crossover.\n",
        "\n",
        "mutation_rate = float(input(\"enter the mutation rate\"))    #a Floating point valuebetween 0 and 1. Example:- 0.01 means that any given chromosome has a 1% chance of being mutated.\n",
        "\n",
        "ratio_of_ridgebuffer_population = float(input(\"enter the ratio of ridgeline population\"))   #a Floating point valuebetween 0 and 1. Example:- 0.25 means 25% of the initial population would be initialized from the ridgeline-buffer.\n",
        "\n",
        "height_of_sensor = int(input(\"enter the height of sensor in metres\"))\n",
        "\n",
        "Global_best_particle = np.zeros((2*no_of_viewpoints)+1)  #it keeps track of the best solution yet obtained at any given point in time.\n",
        "\n",
        "Final_visibility_matrix = np.zeros((size_x,size_y))\n",
        "\n",
        "Best_Particle_by_Epoch = np.zeros((no_of_iterations, (2*no_of_viewpoints)+1))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v6J1IM08zH0k"
      },
      "source": [
        "current_gen=load(\"intial_pop.npy\")\n",
        "#this command requires you to use intial_pop.npy file in directory"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M8zOstyyzH0l"
      },
      "source": [
        "def Fitness(current_generation, global_best_particle):\n",
        "    \n",
        "    for i in range(no_of_particles):\n",
        "        \n",
        "        visibility_matrix = np.zeros((size_x,size_y))   #used to keep track of all the raster cells in the viewshed of any of the censors in a chromosome.\n",
        "        \n",
        "        for j in range(no_of_viewpoints):\n",
        "            ps='1sat'+str(int(current_generation[i][2*j]))+'-'+str(int(current_generation[i][2*j+1]))+'.csv'\n",
        "            filelist=[f for f in os.listdir(str(os.getcwd())) if f==ps]\n",
        "            if len(filelist)==1:\n",
        "                view = pd.read_csv(ps)\n",
        "                for d in view.index:\n",
        "                    x=view['x'][d]\n",
        "                    y=view['y'][d]\n",
        "            \n",
        "                    visibility_matrix[int(x),int(y)]=1\n",
        "                                     \n",
        "                \n",
        "            else:\n",
        "                visibility_matrix = viewshed_gpu(visibility_matrix, int(current_generation[i][2*j]), int(current_generation[i][2*j+1]),fn,radius,size_x,size_y,2)\n",
        "            \n",
        "        \n",
        "        count = 0                                #finding the number of pixels visible.\n",
        "        for k in range(size_x):\n",
        "            for l in range(size_y):\n",
        "                if (visibility_matrix[k][l] == 1):\n",
        "                    count = count+1\n",
        "                    \n",
        "        percentage_covered = count/(size_x*size_y)*100\n",
        "        \n",
        "        current_generation[i][2*no_of_viewpoints] = percentage_covered\n",
        "        \n",
        "    sorted_current_generation = current_generation[current_generation[:,(2*no_of_viewpoints)].argsort()[::-1]]    #sorting the current generation according to fitness.\n",
        "    \n",
        "        \n",
        "    new_Global_best_particle = global_best_particle\n",
        "    \n",
        "    if (global_best_particle[2*no_of_viewpoints] < sorted_current_generation[0][2*no_of_viewpoints]):          #checking for a new global best.\n",
        "        new_Global_best_particle = sorted_current_generation[0]\n",
        "        \n",
        "        \n",
        "    return sorted_current_generation, new_Global_best_particle, current_generation\n",
        "\n",
        "\n",
        "\n",
        "#%%\n",
        "\n",
        "\n",
        "def Selection(Current_generation):    #Stochastic Universal Sampling is used for selection of parents.\n",
        "    \n",
        "    no_of_parents = int(float(crossover_rate * no_of_particles))   #determining the number of parents to be selected for crossover.\n",
        "    \n",
        "    sum_of_fitness = 0\n",
        "    \n",
        "    for i in range(no_of_particles):\n",
        "        sum_of_fitness =  sum_of_fitness + Current_generation[i][2*no_of_viewpoints]\n",
        "        \n",
        "    distance_between_pointers = sum_of_fitness / no_of_parents\n",
        "    \n",
        "    n = random.random() * sum_of_fitness                      #generating a random pointer.\n",
        "    \n",
        "    pointer_array = np.zeros(no_of_parents)\n",
        "   \n",
        "    pointer_array[0] = n\n",
        "    \n",
        "    for i in range(no_of_parents-1):\n",
        "        pointer_array[i+1] = pointer_array[i] + distance_between_pointers \n",
        "        \n",
        "    mating_pool = np.zeros(no_of_parents)\n",
        "    \n",
        "    for i in range(no_of_parents):\n",
        "        \n",
        "        ps = 0\n",
        "        c = -1\n",
        "        \n",
        "        while (ps < (pointer_array[i] % sum_of_fitness)):\n",
        "            ps = ps + Current_generation[c][2*no_of_viewpoints]\n",
        "            c = c+1\n",
        "            \n",
        "        mating_pool[i] = c\n",
        "        \n",
        "    np.random.shuffle(mating_pool)                  #mating pool is shuffled to make crossover happen between random parents in the crossover step.\n",
        "        \n",
        "    return mating_pool                              #mating pool consists of the indices of the chromosomes/parents selected from the current generation for crossover.       \n",
        "    \n",
        "        \n",
        "\n",
        "#%%\n",
        "\n",
        "\n",
        "def Crossover(Current_Generation,Mating_Pool):      #The top chromosomes are carried on as they are from one generation to the other, Rest are replaced by offsprings.\n",
        "    \n",
        "    new_gen = Current_Generation\n",
        "    \n",
        "    t = len(Mating_Pool)\n",
        "    n = no_of_particles - t\n",
        "    \n",
        "    for i in range(0,t,2):                           #since mating pool was shuffled in selection step, consecutive parents crossover is equivalent to random parents mating.\n",
        "        \n",
        "        for j in range(no_of_viewpoints):\n",
        "            \n",
        "            a = random.randint(0,1)                 #if a =1 then first parent gives gene to first offspring, else if a = 0 then first parent gives gene to second offspring\n",
        "            \n",
        "            if (a==1):\n",
        "                new_gen[n+i][2*j] = Current_Generation[int(Mating_Pool[i])][2*j]\n",
        "                new_gen[n+i][2*j+1] = Current_Generation[int(Mating_Pool[i])][2*j+1]\n",
        "                \n",
        "                new_gen[n+i+1][2*j] = Current_Generation[int(Mating_Pool[i+1])][2*j] \n",
        "                new_gen[n+i+1][2*j+1] = Current_Generation[int(Mating_Pool[i+1])][2*j+1] \n",
        "                \n",
        "            else:\n",
        "                new_gen[n+i][2*j] = Current_Generation[int(Mating_Pool[i+1])][2*j]\n",
        "                new_gen[n+i][2*j+1] = Current_Generation[int(Mating_Pool[i+1])][2*j+1]\n",
        "                \n",
        "                new_gen[n+i+1][2*j] = Current_Generation[int(Mating_Pool[i])][2*j] \n",
        "                new_gen[n+i+1][2*j+1] = Current_Generation[int(Mating_Pool[i])][2*j+1]\n",
        "                \n",
        "    \n",
        "    return new_gen                     #consists of the top chromosomes from the last generation and the new offsprings created.\n",
        "\n",
        "\n",
        "#%%\n",
        "\n",
        "\n",
        "\n",
        "def Mutation(current__generation):       \n",
        "    \n",
        "    new_mutated_gen = current__generation\n",
        "    \n",
        "    for i in range(1,no_of_particles):\n",
        "        \n",
        "        b = random.random()\n",
        "        \n",
        "        if (b <= mutation_rate):\n",
        "            print(\"mutated\")\n",
        "            \n",
        "            for a in range(no_of_viewpoints):                          #if any chromosome of the generation is mutated, all of its viewpoints are randomly placed in the buffer area.\n",
        "                \n",
        "                rb = random.randint(0,no_of_ridgeline_points-1)\n",
        "                new_mutated_gen[i][2*a] =  ridgeline_buffer[rb][0]\n",
        "                new_mutated_gen[i][2*a+1] = ridgeline_buffer[rb][1]\n",
        "                \n",
        "            \n",
        "    return new_mutated_gen\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "#%%\n",
        "\n",
        "#running all the iterations for the GA"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kB659eKnzH0r"
      },
      "source": [
        "import time\n",
        "for i in range(51,100):\n",
        "    start=time.time()\n",
        "    \n",
        "    current_gen, Global_best_particle, Current_generation = Fitness(current_gen, Global_best_particle) \n",
        "    \n",
        "    Mating_pool = Selection(current_gen)\n",
        "    \n",
        "    current_gen = Crossover(current_gen,Mating_pool)\n",
        "    \n",
        "    current_gen = Mutation(current_gen)\n",
        "    \n",
        "    print(\"best fitness till iteration \", i+1, \" :- \", round(Global_best_particle[2*no_of_viewpoints], 6))\n",
        "    \n",
        "    Best_Particle_by_Epoch[i] = Global_best_particle\n",
        "    print(\"Iteration Time :-\",int((time.time()-start)/3600), \" Hrs\")\n",
        "    np.save(\"Best_particle.npy\",Best_Particle_by_Epoch)\n",
        "    np.save(\"Current_gen.npy\",current_gen)\n",
        "    \n",
        "    \n",
        "\n",
        "\n",
        "#%%    \n",
        "\n",
        "#Displaying result and making final changes to generate new TIFF file\n",
        "\n",
        "print(\"best solution is : - \\n\" , Global_best_particle)\n",
        "\n",
        "print(\"percentage covered is :- \" , round(Global_best_particle[2*no_of_viewpoints], 6))\n",
        "\n",
        "for v in range(no_of_viewpoints):\n",
        "    x = 0\n",
        "    y = radius\n",
        "    \n",
        "    # Cirlce Points of the final solution generated.\n",
        "\n",
        "    d = int(3 - (2 * radius))\n",
        "\n",
        "    while x<= y: \n",
        "    \n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])+x][int(Global_best_particle[2*v+1])+y] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])-x][int(Global_best_particle[2*v+1])+y] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])+x][int(Global_best_particle[2*v+1])-y] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])-x][int(Global_best_particle[2*v+1])-y] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])+y][int(Global_best_particle[2*v+1])+x] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])-y][int(Global_best_particle[2*v+1])+x] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])+y][int(Global_best_particle[2*v+1])-x] = 1\n",
        "        Final_visibility_matrix[int(Global_best_particle[2*v])-y][int(Global_best_particle[2*v+1])-x] = 1\n",
        "    \n",
        "        if d<0:\n",
        "            d = d + (4*x) + 6\n",
        "        else:\n",
        "            d = d + (4*(x-y)) + 10\n",
        "            y = y-1\n",
        "        x = x+1\n",
        "        \n",
        "        \n",
        "    Final_visibility_matrix = Viewshed(Final_visibility_matrix, int(Global_best_particle[2*v]), int(Global_best_particle[2*v+1]) )\n",
        "\n",
        "\n",
        "#%%\n",
        "from numpy import save\n",
        "save('result.npy',Final_visiblity_matrix)\n",
        "\n",
        "with open('Results/Sensor Positions After Each Epoch.csv', 'w', newline='') as f:\n",
        "    writer = csv.writer(f)\n",
        "    writer.writerows(Best_Particle_by_Epoch)"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}