Skip to content

BestProductionFirstGiveUpGiveInAllocationModel

Jump to bottom
Bumsuk Seo edited this page Sep 30, 2020 · 3 revisions

Overview

  • [Overview]
  • [Operation]
  • [Parameters]
  • [Configuration Example]
  • [Performance]

This model is implemented to speed up the process of giving in in a realistic way: as cells are sampled with those promising high production for the seeking potential agent first, potential agents should be able to take over sooner, requiring less cells to be examined.

Operation

Each timestep, the model does the following:

  • For each empty cell, introduces the most competitive potential agent to fill the cell (as per the SimpleAllocationModel)
  • For each potential agent, cells are sorted according to their potential production of the potential agents main service (the one with highest productivity) for the particular potential agents. The set is updated when
    • effective capitals of a cell change (removal and re-addition of the cell into the sorted set).
    • a potential agent's production changes, e.g. due to innovation (the entire set for that potential agents is re-initialised).
  • numTakeovers times, the set of PotentialAgents is sampled according to their competitiveness on a perfect cell (raised to an exponent): P(a)=Comp(a)^b. This is done for every time to account for changes in supply. Then
    • The first cell is sampled from the set of ordered cells for the selected potential agent, by applying a set probability to each cell (defined by probabilitycurve and possibly depending on the index to be selected) starting from the top. To ensure the defined number of searched cells can be sampled the following function is applied: p = max(probabilitycurve(index), numberStillToSample/(length - index - 1))
    • The potential agent attempts to force out the current agent in the sampled cell. Currently, DefaultAgents decide whether to give in by comparing the new agent's competitiveness with their own, plus their Giving In threshold. If the new value is higher, they give in.
    • If it succeeds, the loop terminates. Otherwise it continues until numCells cells have been sampled.

Compared to GiveUpGiveInAllocationModel this model

  • does not completely randomly sample numCells cells from all cells but one after another according to the production of a potential agent's main service
  • does not compute competitiveness of numCells for each take over but maintains a set of sorted cells per potential agent
  • is supposedly more efficient, more accurate in obtaining the sample of searched cells from all cells, but less accurate in ordering cells in the subset of searched cells (since it considers production of main service instead of competitiveness).
  • The concept of bounded rationality is respected by the fact that the set of ordered cells is not walked trough one by one, but each cell starting from top to bottom is considered with a set probability (0.5 per default).

Parameters

Name Type Default Batch-mode ready Descritpion
numCells String NaN yes The number of cells an agent (type) can search over to find maximum competitiveness
percentageCells String NaN yes Alternative to numCells: specify the percentage of entire cells in the region to search over.
numTakeovers int 30 no The number of times an agent (type) can search the above no. of
probabilityExponent int 2 no The agent's competitiveness is raised to this power
samplerFactory IterativeCellSamplerFactory IterativeCellSamplerFactory no The IterativeCellSamplerFactory provides IterativeCellSampler and holds probabilitycurve which is passed to them and determines the probability by which each cell is considered.

Configuration Example

<allocation class="org.volante.abm.example.BestProductionFirstGiveUpGiveInAllocationModel" 
        percentageCells="15" numTakeovers="10" probabilityExponent="2">
    <samplerFactory class="org.volante.abm.example.IterativeCellSamplerFactory">
        <probabilitycurve class="com.moseph.modelutils.curve.Constant" value="0.5"/>
    </samplerFactory>
</allocation>
  • numTakeovers: how many times is an agent selected and attempts to take over a cell
  • numCells: how many cells an agent can search per "takeover"
  • probabilityExponent: the agent's competitiveness is raised to this power. pE = 0 gives equal chance, raising it makes it increasingly likely that highly competitive agents get selected over less competitive ones.

Performance

Since java SE versions before java 8 (which is not available on Eddie in 09/2015) do not include a sorted, indexed collection which is required to efficiently keep the set of cells sorted and accessible by random indices, several implementations very tested and compared to other AllocationModel versions, and showed huge differences:

 | Benchmark | Samples | Score | Score error | Units | |-------------------------------------------------------|----------|--------|--------------|--------| | c.StageABenchmarking.allocationFxBestFirstGi | 10 | 0.839 | 0.548 | s/op | | c.StageABenchmarking.allocationJidesoftBestFirstGi | 10 | 2.296 | 1.862 | s/op | | c.StageABenchmarking.allocationScottlogicBestFirstGi | 10 | 6.137 | 2.712 | s/op | | c.StageABenchmarking.allocationGIRandom | 10 | 3.918 | 1.575 | s/op | | c.StageABenchmarking.allocationGISorted | 10 | 4.459 | 1.854 | s/op |

(Tests performed in project CRAFTY_Testworld with JHM)

Since JavaFx SortedSet is by far the most efficient version it was backported to java 7 using retrolambda and is available in CRAFTY_Parallel.

Clone this wiki locally