0

I am trying to find the best solution for radar placement problem with using multi objective simulated annealing algorithm. So there is an area (in real map) and I want to put minimum count of radar as possible with the maximum area coverage. I am using multi-objective simulated annealing algorithm to do that and in small maps it works well, but when the map size increases the solution size also increases and updating it for better solutions. It becames hard to find a good solution at the end and the calculation times increases a lot.

The problem is here. What should I do to reduce the solutin size? For example my real world map is 250x500 and the solution size is 250x500 = 125000. It is hard to seperate radars randomly at on solution with this high size, it doesn't work well and consumes a lot of time. How can I reduce that solution size? For example, there are 125k different possible place to put a radar, but if it become 1k or 10k different place, it becomes easier to get a good result.

TarabydaVllasıCafcaflıAtArabsı
  • 1
  • so its just placement binary matrix (or vector)? supposedly sparse matrix, one simple trick crossed my mind is segment the solution into 16 bits and represent that 16 bits as integer [0.2^16-1]. In other words, find other solution representation, maybe binary vector compression also can come in handy. – Sanyou Jan 17 '22 at 07:04
  • @Sanyou my solution is a binary vector like this: [0,0,0,1,0,0,0,0,0,1,......,0], I could not understand well how can I represent this with 16 bit representation. – TarabydaVllasıCafcaflıAtArabsı Jan 17 '22 at 07:24
  • every N bit u turn it into [0,2^N-1] integer. example: 2x4 dimensions, and N=4. x = [0,0,1,0, 1,0,0,1]. x' = [2,9]. 0,0,1,0 => 2. 1,0,0,1 => 9 – Sanyou Jan 17 '22 at 07:46
  • @Sanyou iy my solutions the bits represents just one place and 1=true, 0=false. if it is true there is placed a radar. So "1" represents "there is placed a radar". After all I look at where are 1's and calculate the coverages of areas. Your suggestion is logicfull but doesn't solve my problem. – TarabydaVllasıCafcaflıAtArabsı Jan 17 '22 at 08:30
  • maybe you missed that besides encoding (binary vector into sequence of integer), you also can decode (sequence of integer into binary vector). Now if you can define simulated annealing operation for the sequence of integer (or any other solution representation you choose), then your optimization process will be the same as the previous one but with smaller solution's size. – Sanyou Jan 17 '22 at 15:35

0 Answers0