Biologist hat on

PREAMBLE:

Moving forward the intent will be to add more focused (hopefully smaller) posts. Effectively each post should be constrained as much as possible to one specific area. This may mean that a long session of work/research may have to be split up into separate posts however I believe the additional effort will pay off in future. When I am trying to look up previous work in a certain category, it will ensure the majority of each post with that tag is relevant, as opposed to returning posts with a small bit on the category I am looking for buried amongst other elements of the problem. A ‘weekly summary’ or similar may still be worthwhile.

AIM:

Develop options for representing the solution data into the Evolutionary Algorithm (EA).

CONDUCT:

  • Ongoing discussion and ‘thought experiments’

RESULTS:

The general solution will consist of a Form Up Point (FUP) and a Support By Fire (SBF) location. The pathing to these locations will be handled by the pre calculated flow field so the solution encoding only requires the two locations. The problem then becomes how to represent these locations.

Options:

  • No pre processing of solution space:
  • Every single point in the terrain data can be considered for both FUP and SBF regardless of suitability (eg. Points in the open in front of the enemy position)
    • Each location represented by 2 integers corresponding to coordinates
      • eg. FUP (2, 17) and SBF (45, 32) represented as (2, 17, 45, 32)
      • Crossover has 4 options
      • Mutation can move one of four integers left/right
      • Somewhat limited
    • As above but locations are represented by n bit binary representations of each coordinate (n based on the size of the largest dimension)
      • eg. Using same FUP/SBF locations in 8 bit representation:
      • (00000010, 00010001, 00101101, 00100000) or
      • (00000010000100010010110100100000)
      • This solution offers significantly more crossover options ranging from the same as previous (keeping the 8 bit representations as one ‘whole’ bit to crossover) to smaller resolutions (eg. each integer has two four bit parts which can be used for crossover)
      • More importantly, it offers significantly better options for mutation: a random bit can be swapped between 1 and 0 which will result in a (potentially) large mutation due to the binary representation. This can be controlled; more significant bit mutation represents a larger solution mutation whereas a less significant bit will correspond to a smaller overall mutation.
      • Notable issue: This method can result in child solutions that lie outside the solution space. eg. If the locations are represented by 8 bits (unsigned) then the maximum value is 255. If the actual terrain is smaller than this (eg. the 100m x 100m test terrain) a mutated bit (or unlucky crossover) could result in a coordinate outside the terrain. This can obviously be checked after mutation or have the resulting child ‘die off’ immediately however it is still potentially wasted processing time.
  • Pre processing of solution space. 
  • During viewshed calculation, FUP and SBF solution candidate lists are populated based on that point’s viewshed result. This will remove tactically unsound points from the candidate solution pool prior to the population of the EA.
    • Each location represented by a SINGLE integer which corresponds to the index of the location in the candidate list.
      • eg. FUP (2, 17) and SBF (45, 32) may be represented in the candidate lists as candidateFUP[3] and candidateSBF[9] thus they would be represented in the EA as (3, 9)
      • This results in minimal crossover options (one from each parent)
      • This also results in minimal mutation options (incrementing or decrementing one of two integers)
    • As above but each integer represented by the binary representation of n bits (n based on the total size of the largest array)
      • Using the above example, the encoding would be (in 4 bit encoding)
      • (0011, 1001) or (00111001)
      • This offers the same advantages as per the previous binary representation without pre processing however it also suffers from the same issue: if the total size of the largest array is 70 then the encoding will be 7 bits. This can still result in indexes evolving that are outside the array length (especially notable if one array is much smaller than the other)

The above points are still under consideration however at this stage I am leaning towards the final one (pre processing and binary index representation).

The viewshed pre processing is required for pathing calculations regardless and it seems to be a significant waste of effort to not take advantage of that step to prepopulate solution candidate lists at the same time. This will be negligible computational cost (merely the additions to the lists) and save potentially significant time spent outside the tactically sound solution space (which is effectively outside the solution space anyway).

The additional processing required to confirm the mutation remains in the solution space and either kill it off or amend it if it doesn’t is likely to be much less than the additional computations spent outside the solution space without preprocessing.

 

TIME SPENT:

2 hours (20 hours running total)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s