BuscaLocal.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "from matplotlib.mlab import griddata\n",
    "from matplotlib import cm\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Problema(object):\n",
    "    \n",
    "    estado_inicial = None\n",
    "    \n",
    "    def vizinhos(self, estado):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def sol_otima(self):\n",
    "        return None\n",
    "\n",
    "class BuscaLocal(object):\n",
    "    def __init__(self):\n",
    "        self.estados = []\n",
    "    \n",
    "    def buscar(self, problema):\n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def log_estado(self, estado):\n",
    "        self.estados.append(estado)\n",
    "        \n",
    "    def plot_valores(self):\n",
    "        plt.figure()\n",
    "        valores = map(lambda x: x.valor, self.estados)\n",
    "        plt.plot(np.arange(len(self.estados)), valores)\n",
    "        plt.ylabel('Valor')\n",
    "        plt.xlabel('Iteracao')\n",
    "        plt.show()\n",
    "\n",
    "class Estado(object):\n",
    "    def __init__(self, valor):\n",
    "        self.valor = valor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class EstadoPSVM(Estado):\n",
    "    def __init__(self, valor, e, d):\n",
    "        super(EstadoPSVM, self).__init__(valor)\n",
    "        self.e = e\n",
    "        self.d = d\n",
    "    \n",
    "    def __str__(self):\n",
    "        return 'E=%d, D=%d, S=%s' % (self.e, self.d, self.valor)\n",
    "        \n",
    "class ProblemaSubVetorMaximo(Problema):\n",
    "    \n",
    "    @classmethod\n",
    "    def from_aleatorio(cls, n_elementos, e_inicial=None, d_inicial=None, r_seed=None):\n",
    "        rs = np.random.RandomState(r_seed)\n",
    "        \n",
    "        cls.vetor = rs.randint(-100,100,(n_elementos))\n",
    "        \n",
    "        if not e_inicial:\n",
    "            e = rs.randint(0, n_elementos-1)\n",
    "            d = rs.randint(e, n_elementos)\n",
    "        else:\n",
    "            e = e_inicial\n",
    "            d = d_inicial\n",
    "        valor_ini = ProblemaSubVetorMaximo.__valor_solucao(cls.vetor,e,d)\n",
    "        cls.estado_inicial = EstadoPSVM(valor_ini, e, d)\n",
    "        return cls()\n",
    "    \n",
    "    @classmethod\n",
    "    def from_vetor(cls, vetor, e_inicial, d_inicial):\n",
    "        cls.vetor = vetor\n",
    "        cls.estado_inicial = EstadoPSVM(ProblemaSubVetorMaximo.__valor_solucao(vetor,e_inicial, d_inicial), e_inicial, d_inicial)\n",
    "        return cls()\n",
    "        \n",
    "    @staticmethod\n",
    "    def __valor_solucao(v, e, d):\n",
    "        return np.sum(v[e:d+1])\n",
    "    \n",
    "    def valor_solucao(self, e, d):\n",
    "        return ProblemaSubVetorMaximo.__valor_solucao(self.vetor, e, d)\n",
    "    \n",
    "    def vizinhos(self, estado):\n",
    "        vizs = []\n",
    "        e = estado.e\n",
    "        d = estado.d\n",
    "        for i in [e-1,e,e+1]:\n",
    "            if (i < 0) or (i >= self.vetor.shape[0]):\n",
    "                continue\n",
    "            for j in [d-1,d,d+1]:\n",
    "                if (j < 0) or (j >= self.vetor.shape[0]):\n",
    "                    continue\n",
    "                if (e == i) and (d == j):\n",
    "                    continue\n",
    "                vizs.append(EstadoPSVM(self.valor_solucao(i,j), i, j))\n",
    "        return vizs\n",
    "    \n",
    "    def sol_otima(self):\n",
    "        #Find maximum subarray (Cormen)\n",
    "        def fmsa(V, e, d):\n",
    "            #print (e, d)\n",
    "            if e == d:\n",
    "                return (e, d, V[e])\n",
    "            else:\n",
    "                meio = int(math.floor((e + d) / 2))\n",
    "                \n",
    "                eb, ea, es = fmsa(V, e, meio)\n",
    "                db, da, ds = fmsa(V, meio + 1, d)\n",
    "                cb, ca, cs = fmcsa(V, e, meio, d)\n",
    "                if (es >= ds) and (es >= cs):\n",
    "                    return (eb, ea, es)\n",
    "                elif (ds >= es) and (ds > cs):\n",
    "                    return (db, da, ds)\n",
    "                else:\n",
    "                    return (cb, ca, cs)\n",
    "        \n",
    "        def fmcsa(V, e, m, d):\n",
    "            es = -np.infty\n",
    "            s = 0\n",
    "            for i in range(m, e-1, -1):\n",
    "                s += V[i]\n",
    "                if s > es:\n",
    "                    es = s\n",
    "                    em = i\n",
    "            ds = -np.infty\n",
    "            s = 0\n",
    "            for j in range(m+1, d+1):\n",
    "                s = s + V[j]\n",
    "                if s > ds:\n",
    "                    ds = s\n",
    "                    dm = j\n",
    "            return (em, dm, es + ds)\n",
    "                    \n",
    "        solucao = fmsa(self.vetor, 0, self.vetor.shape[0]-1)\n",
    "            \n",
    "        return EstadoPSVM(solucao[2], solucao[0], solucao[1])\n",
    "    \n",
    "    def plot_espaco_estados(self, estados):\n",
    "        X = np.array(map(lambda x: x.e, estados))\n",
    "        Y = np.array(map(lambda x: x.d, estados))\n",
    "        Z = np.array(map(lambda x: x.valor, estados))\n",
    "        \n",
    "        xi = np.linspace(min(X), max(X))\n",
    "        yi = np.linspace(min(Y), max(Y))\n",
    "        \n",
    "        xx, yy = np.meshgrid(xi, yi)\n",
    "        zz = griddata(X, Y, Z, xi, yi, interp='linear')\n",
    "        \n",
    "        plt.pcolormesh(xx,yy,zz, cmap=cm.jet)\n",
    "        plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HillClimbingBL(BuscaLocal):\n",
    "    \n",
    "    def __init__(self, tolerancia=None):\n",
    "        super(HillClimbingBL, self).__init__()        \n",
    "        self.tolerancia = tolerancia\n",
    "    \n",
    "    def buscar(self, problema):\n",
    "        atual = problema.estado_inicial\n",
    "        it = 0\n",
    "        estag = 0\n",
    "        melhor = None\n",
    "        while True:\n",
    "            print('###Iteração %d###' % it)\n",
    "            vzs = problema.vizinhos(atual)\n",
    "            print_vizinhos(vzs)\n",
    "            vizinho = max(vzs, key=lambda x: x.valor)\n",
    "            print('Vizinho escolhido: %s' % vizinho)\n",
    "            \n",
    "            if not self.tolerancia:\n",
    "                if vizinho.valor <= atual.valor:\n",
    "                    return atual\n",
    "            atual = vizinho\n",
    "            \n",
    "            if melhor is not None:\n",
    "                if atual.valor > melhor.valor:\n",
    "                    melhor = atual\n",
    "                    estag = 0\n",
    "                else:\n",
    "                    estag +=1\n",
    "                    if estag > self.tolerancia:\n",
    "                        return melhor\n",
    "            else:\n",
    "                melhor = atual\n",
    "            \n",
    "            self.log_estado(atual)\n",
    "            \n",
    "            print('Estado atual: %s' % atual)\n",
    "            if self.tolerancia:\n",
    "                print('Melhor estado: %s' % melhor)\n",
    "            print('')\n",
    "            it+=1\n",
    "            \n",
    "\n",
    "def print_vizinhos(estados):\n",
    "    print('Vizinhos')\n",
    "    for e in estados:\n",
    "        print('\\t%s' % (e))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#p = ProblemaSubVetorMaximo.from_aleatorio(10)\n",
    "\n",
    "#v = np.array([13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7])\n",
    "#p = ProblemaSubVetorMaximo.from_vetor(v, 5, 12)\n",
    "\n",
    "p = ProblemaSubVetorMaximo.from_aleatorio(50, e_inicial=20, d_inicial=24, r_seed=50)\n",
    "\n",
    "hc = HillClimbingBL(tolerancia=10)\n",
    "\n",
    "print(p.vetor)\n",
    "print ('Estado Inicial: %s' % p.estado_inicial)\n",
    "\n",
    "solucao = hc.buscar(p)\n",
    "\n",
    "print(\"Solução: %s\" % solucao)\n",
    "\n",
    "sol_otima = p.sol_otima()\n",
    "print ('Solução ótima: %s' % sol_otima)\n",
    "\n",
    "hc.plot_valores()\n",
    "\n",
    "p.plot_espaco_estados(hc.estados)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}