#### Back

# Neighborhood Search

### Implementation

```
import System.Random
import System.IO.Unsafe
import Control.Monad ( replicateM)
```

The first thing that should be done is to write some helper-functions for generating pseudorandom numbers. To do that, I’ll start by defining **seed** for random generators and a function that will generate a finite length list of values in range, `getRandomValuesInRange::Int->Int->Int->IO [Int]`

. For exercise purpose only, I’ll define second function that will return a finite length list of doubles, uniformly distributed on , `getRandomValues::Int->[Double]`

.

```
seed::Int
seed=(-958036805781772734)
```

```
getRandomValues :: Int -> [Double]
getRandomValues len=take len $ randoms (mkStdGen seed)::[Double]
```

```
getRandomValuesInRange::Int->Int->Int->IO [Int]
getRandomValuesInRange len a b = replicateM len (getStdRandom $ randomR (a,b))
```

Since `getRandomValuesInRange`

returns a `IO`

list of integers, I’ll define a wrapper that will return a list of integers. The wrapper will abuse of `unsafe IO`

. In a future implementation this wrapper will be removed and all operations will be performed safe.

```
getRandomValueUnsafe::Int->Int->Int->[Int]
getRandomValueUnsafe len a b =unsafePerformIO $ getRandomValuesInRange len a b
```

Now, I need to define the characteristics of an item. In case of knapsack problem, each item has a **weight** and a **value**. Considering this, I’ll define a new type **Item** which will be a tuple of weight and value. To be mentioned that instead of using `newtype`

I could use `type`

. The reason behind not choosing `type`

is that I don’t want to tightly couple the implementation with the problem.

```
newtype Item = Item { rawItem::(Int,Int) } deriving (Show,Eq)
```

Next step is to define a generic datatype for the possible solutions. For a simple problem like knapsack the solution can be a list of binary values.

```
newtype Solution = Solution { rawSolution::([Int],Int)} deriving (Show,Eq)
```

Normally, the next step should be to define a fitness function but that would make the implementation tightly coupled with the problem that solves. For example, if the implementation is needed to solve the knapsack problem, one of the parameters needed to be passed to the fitness function should be the dataset. Instead, a new type for dataset will be defined.

For knapsack problem, dataset can be a list of tuples `(g,v)`

where is the weight of the object and is the value of the object.

```
newtype Dataset = Dataset { rawDataset::(Int,[Item])} deriving (Show,Eq)
```

Now a generic fitness function can be defined:

```
fitness::Dataset -> Solution -> Int
fitness dataset solution = fitnessValue
where
datasetRaw = rawDataset dataset
maxWeight = fst datasetRaw
items = map rawItem (snd datasetRaw)
individual = fst $ rawSolution solution
pairs = zip individual items
weight = foldl (\acc x-> if fst x==1 then acc+fst (snd x) else acc+0) 0 pairs
value = foldl (\acc x-> if fst x==1 then acc+snd (snd x) else acc+0) 0 pairs
fitnessValue = if weight <= maxWeight then value else 0
```

Ok, it’s not a complicated function but there are a lot of operations that are performed on lists for calculating the fitness value. Step by step is:

- It accepts 2 parameters of types Dataset and Solution, respectively
`datasetRaw = rawDataset dataset`

-> get the tuple (G,[(g,v)]), where G is Maximum Weight, g is item’s weight and v is item’s value.`maxWeight = fst datasetRaw`

-> get the maximum weight from the tuple`items = map rawItem (snd datasetRaw)`

-> get the list [(g,v)]`individual = fst $ rawSolution solution`

-> extract the individual configuration from solution`pairs = zip individual items`

-> create pairs of type [(is_item,(g,v))]`weight = foldl (\acc x-> if fst x==1 then acc+fst (snd x) else acc+0) 0 pairs`

-> extract total weight for solution`value = foldl (\acc x-> if fst x==1 then acc+snd (snd x) else acc+0) 0 pairs`

-> extract total value for solution`fitnessValue = if weight <= maxWeight then value else 0`

Before implementing the function that will calculate the best neighbor in neighborhood, I will need some “helper functions”.

`replaceNth`

is used to replace the value of element in a list with a new value.`maximum'`

is a function that will get the maximum element from a list of tuples.`calculateNeighborhood`

is used to calculate the neighborhood of a solution.

```
replaceNth::Int -> Int->[Int]->[Int]
replaceNth _ _ [] = []
replaceNth index newVal (x:xs)
| index==0 = newVal:xs
| otherwise = x:replaceNth (index-1) newVal xs
```

```
maximum'::[([Int],Int)]->([Int],Int)
maximum' [] = error "empty list"
maximum' (x:xs) = maxTail x xs
where maxTail currentMax [] = currentMax
maxTail (m,n) (p:ps)
| n<(snd p) = maxTail p ps
| otherwise = maxTail (m,n) ps
```

```
calculateNeighborhood::(Dataset->Solution->Int)->Dataset->Solution->Int->[([Int],Int)]->[([Int],Int)]
calculateNeighborhood _ _ _ 0 neighbors = neighbors
calculateNeighborhood f dataset solution len neighbors = calculateNeighborhood f dataset solution (len-1) (neighbor:neighbors)
where
raw = fst $ rawSolution solution
newNeighbor = if raw !! (len-1) == 1 then replaceNth (len-1) 0 raw else replaceNth (len-1) 1 raw
fitnessValue = f dataset (Solution (newNeighbor,0))
neighbor = (newNeighbor,fitnessValue)
```

Now the implementation of the function that will calculate the neighborhood can be done. The function will receive as parameters a fitness function, the dataset, current solution and will return a new solution. In other words, the function’s type will be `getNewNeighbor::(Dataset->Solution->Int)->Dataset->Solution->Solution`

```
getNewNeighbor::(Dataset->Solution->Int)->Dataset->Solution->Solution
getNewNeighbor f dataset solution = result
where
rawList = fst $ rawSolution solution
neighbors = calculateNeighborhood f dataset solution (length rawList) []
result = Solution (maximum' neighbors)
```

Now, since the the `getNewNeighbor`

and `fitness`

functions are implemented, I can define the neighborhood search function.

```
kn::Dataset->Solution->Int->Solution
kn dataset solution numberOfItems
| snd (rawSolution newSolution) > snd (rawSolution solution) = kn dataset newSolution numberOfItems
| otherwise = solution
where newSolution = getNewNeighbor fitness dataset solution
```

### Example

Let’s consider a backpack with a maximum capacity of 10 kilograms. There are 4 items with the following characteristics:

- Item having 6 kg and a value of 50 $
- Item having 5 kg and a value of 90 $
- Item having 2 kg and a value of 20 $
- Item having 4 kg and a value of 30 $

```
dataset=Dataset (10,[Item (6,50), Item (5,90),Item (2,20),Item (4,30)])
```

```
randomValues = Solution (getRandomValueUnsafe 4 0 1,0)
```

```
randomValues
```

```
Solution {rawSolution = ([0,1,0,0],0)}
```

```
fitnessInitial = fitness dataset randomValues
initialSolution = Solution (fst $ rawSolution randomValues,fitnessInitial)
```

```
initialSolution
```

```
Solution {rawSolution = ([0,1,0,0],90)}
```

```
kn dataset initialSolution 4
```

```
Solution {rawSolution = ([0,1,0,1],120)}
```