What does cdf() stand for?

[maxnation]

Hi! I've been investigating AIS for some time and met your project. Cool job! I'd be glad if you could answer a couple of questions. In the code below, are you actually computing common distribution function and what is the goal? Is there any work with probabilities in the proposed model?

in CLONALG.py : `def cdf(how_many, b):

weights calculated on the basis of the parabola of the quadratic equation with the given parameter b: ax^2 + bx + c = 0

# b should be within the range (1,2)
assert 2 > b > 1
result = []
for i in range(1, how_many):
    result.append((1 - b) * (i / how_many) ** 2 + b * (i / how_many))
return result`

If that is an actual CDF computation, could you please explain in more detail, how was the 'b' range (1,2) obtained and what does expression in result.append(...) mean? Thanks in advance and have a good luck!

[maxnation]

it seems that you'll be notified only when mentioned @ArturBa

[ArturBa]

@Kamil1309 is an author of that part

[maxnation]

@Kamil1309 would be glad to get your feedback

[Kamil1309]

Hi, @maxnation I'll try to answer you. The goal was to select one individual from the population but we didn't want the same probability for everyone. And we wanted a distribution that gives more chances to choose smaller indexes. So how can we do that? We couldn't just draw an random index (that would be 'discrete uniform distribution').

I thought about this part of quadratic function. Example: Let's assume you have 5 individuals in your population. And you got quadratic function: y = -0.5 x^2 + 1.5 x (I will explain why function is in that form later). We calculate 4 values: y(1/5) = 0.28, y(2/5) = 0.52, y(3/5) = 0.72, y(4/5) = 0.88. These values divide the range from 0 to 1 into 5 parts of varying size, where the next part is smaller than the previous one. Now with that division we can random value from 0 to 1, and by using bisect.bisect we can indicate the appropriate index. For example we take random value val = 0.51, then bisect will return 1 (first index, we chose an individual with the first index to mutate it). So in this example we just changed 'discrete uniform distribution' on "discrete non uniform distribution" so the chances of selecting the next indexes have changed from [0.2 0.2 0.2 0.2 0.2] to [0.28 0.24 0.2 0.16 0.12].

Ok, so now why its this quadratic function and why b is in (0, 1). I was interested in the quadratic function between 0 and 1 that satisfies y(0) = 0 and y(1) = 1. From first we got c = 0, and then from second one we got a = 1 - b. So we got (1 - b) * (x)^2 + b * x. When we have such a function we need to determine what 'b' it can take. If b is under 1 then the parabola inverts and the chances of selecting a smaller index become less than that of selecting a larger one, so we dont want that. If b is greater than 2 then the x-component vertex of the parabola shifts between 0 and 1, which can lead to the situation where our division looks like [0.3 0.5 0.65 0.7 0.65 0.5 0.3], so values go up first and then go down and it's not effect that we want.

[maxnation]

@Kamil1309 Thanks for such a great explanation!

In the code You used b = 1.5 , did you choose a random valid value or it was somehow empirically obtained?

If You don't mind, I'd like You to explain a little bit about tests. In the report at the beggining of the section '5 Testy' the best value is 1612,46 for 183 iterations (with default algorithm parameters). But for each run the population is generated randomly, so it's possible to obtain even a higher best value (just now I obtained 1678.33 for less iterations). According to this, the best values In Table 2 are best for a single run, but not the best possible? If rely on results of just one run and obtain pretty different results with the same parameters, one can reasonably draw other conclusions about the influence of the parameters (as test results with the same parameters may differ by half) Did not you consider to somehow aggregate the bests values of multiple runs with set parameters?

[Kamil1309]

@maxnation yes, 1.5 was just random value :D

You are absolutely right. 1612.46 is best value just from random run, best we had in all tests is 1825.85 if I'm right. And yes in Table 2 we also did only one run for every parameter value so the results don't reflect reality as well as they could. But it was small project and we didn't pay so much attention to the tests, if we would do that for serious there could be hundreds or thousands of tests. And I think with our code this kind of an extension is not a problem. If you try it and you get interesting results, I'll be glad to see them :D

[maxnation]

@Kamil1309 It's definetely worth trying! 😄 Thanks a lot for your time!

[Kamil1309]

Thank you for your interest <3 You surprised us with that in a positive way :D If you have any more questions, feel free to write ;)

[maxnation]

@Kamil1309 Hi! Sorry for disturbing you again :D I'm trying to sort out how the factory class works, I would be glad if you could help me. (the following questions are related to Factory.run() and the methods it uses)

1. Is there any need to reset initial values (# reset inial values)?

2 Next you're checking whether the time to produce required quantity of items is less than time of factory work (per day?) (same for big_machine) in calc_time_for_req, let's assume that machine.parts_required = 60 and machine.machine_count = 8, so 60/8 = 7.5, but due to math.ceil() we're getting 8. That means we returning required time not for 60 parts, but for 64. Thus, we set the elapsed time for that higher quantity of parts, but the quantity of created parts is set equal to required_parts I guess here the created_parts should be equal to ceil(machine.parts_required / machine.machine_count)*machine.machine_count , am I right? Otherwise, can machine produce non-integer number of parts (7.5 as in example)? Acording to subject are, it doesn't seem like this :D

3. In the section # additional parts The additional parts are produced while there is enough spare material to produce al least one part of small or big type and small or big machine(s) have remaining time to work. That is where I failed to grasp the idea of how the algorithm works D: Why to check which type of machines finished first? Could you please explain what's going on in first_cycle() and in regular_cycle() ?

is this a valid expression? Can't figure out what it means to subtract the remainder from division from the number of machines (and what's going all at all :D)

4. Why using multi in calc_value ? As I understand, if the quantity produced is twice (as 'multy' passed is 2) higher than necessary, than the value of single unit decreases.

Sorry for so many questions (Maybe you have a verbose flowchart or source to read? :D ) Thanks in advance!

[wifilipiak]

@maxnation 1 It wasn's really needed because reseting initial values only matters when you use run() of the same object multiple times which is pointless(But better to be safe than sorry :D)

2 You are right that the number of parts in this moment can be wrong because of ceil but it's corrected later in first_cycle(). It's done like this because we had additional requirement which said: We must make sure that all required parts can be done before wasting material on spare parts. Also we don't include cost of fuel/power to run machines in our calculations, so we can safely assume that all machines are running as long as at least one is producing something.

3 We are calculating time and material for required parts all at once because we know that there must be enough material to produce all of them and at worst we can run out of time. But spare parts are calculated cycle by cycle in a loop so checking which machine finished first is important. Small and big machines work independently and can have different cycle time, also our main constraint is material, so machines of type which finished first have right to use it before the other type.

First_cycle() of spare parts is actually the same as last cycle of required parts production. Let's use the situation you wrote about:

in calc_time_for_req, let's assume that machine.parts_required = 60 and machine.machine_count = 8, so 60/8 = 7.5, but due to math.ceil() we're getting 8. That means we returning required time not for 60 parts, but for 64.

In last cycle only 4 parts were needed but there were 8 machines, if there was still material available those additional 4 machines could already start producing spare parts. In expresion: machine.machine_count - machine.parts_required % machine.machine_count remainder from division is the number of required parts in last cycle (we are excluding 0 in if statement), and the difference is the number of free machines. I know that it's not really intuitive but we are doing this because there can be situations where only part of free machines can work on spare parts or even none (lack of material).

Now regular_cycle() is the cycle after all required parts were made so all machines are free to produce spare parts. We check if there is enough material for all of machines to work or only for some of them. Then we check if there is enough time, while also checking if workers' shift changes during that cycle (we must add preparation time in this case)

4 You understand it correctly. We used it to make all-in situation not optimal. Some excess parts are ok (in our case twice the amound required) but producing too much parts should not be profitable. The dimnished value of excess parts was arbitrary.

I hope I explained it well enough. If you have any other questions feel free to ask.

[maxnation]

@wifilipiak Thanks a lot! I think at this line we are hopelessly wasting a time of work? (same for the case when shifts don't change) Assume that elapsed_time= 7h30m , real_runtime =1h, prep_time = 1h45m and max_time = 9h. As 7h30m + 1h + 1h45m > 9h, we are falling into the else block. 30m of shift are gone idle, am I right? Moreover, doing here machine.elapsed_time = max_time would set extra 1h30m of work, which weren't actually spent as work

[maxnation]

Oh, I should have checked first whether it's possible to get elapsed time like this with given prep_time and realtime. So let's consider some valid elapsed_time, what would that 'else' block mean? I guess we are about to lose some time here anyway

[wifilipiak]

@maxnation That elseblock prevents from doing cycles which would take more time than we have available (max_time = factory working time) . Only full cycles produce parts as we can't produce non-integer number of parts. So basically it's wasting time but it's the only thing we can do here (setting elapsed_time to max_time is needed to escape while loop in run()).