Skyrim? Son, if I knew about this in 1999 I'd SOJs on SOJs in D2...

Shiniest stuff first. Always. After that then apply a genetic algorithm, obviously, but not until the shiny stuff is all taken, even if that means you have to walk all the way back to Whiterun.

15 forks, a wheel of cheese, some clothes you cant wear, and a cabbage.

This problem is simpler than skyrim tho. With skyrim, you won't know all the items ahead of time, rather you get item and have to keep or discard without knowing future items.

Take the calipers, only the calipers; leave everything else. Problem solved. (Still looking for calipers in Skyrim.)

you are Bruno Ribeiro

hahahahahhah

@@opkp yyyup.....?

evolution also takes millions of years . GA will converge to a global optimum , given enough time and a very big population

@@gerritgovaerts8443 hm

@@gerritgovaerts8443 hm

Oh my I am litterally trying exactly that right now, I didn't imagine anyone else had the same idea before

@@gerritgovaerts8443 not really, if the mutation rate and crossover is not well selected it might reach a local optimum and never reach a global optimum

Right?

I needed this

Thank you! I re-listened to that bit like 5 times trying to figure out what he was saying.

Thank you.

Ah! The famous Bergan. Never heard of it, so thanks!

source?

Backpack

It's like a cloth portmanteau that closes with a zip rather than buckles. ;-)

@@violet_flower Heyooooo!

Don't worry, I sent him a note informing him of a more general, if somewhat obscure term: "Bag"

It's like a haversack.

I mean, the standard solution is to use dynamic programming and a memo. The worst case is still no better than brute force, but it usually does pretty well.

You are right but incidentally you are also defining a problem for which a genetic algorithm would be excellent solution (assuming that it was faster to compute, perhaps not a genetic algorithm itself).

I thought he was about to write out a table and do the classic dynamic solution to the napsack problem lol

I thought same

You can also tell whos a compsci undergrad, prolly 3rd-4th year with this problem. They all scream DYNAMIC PROGRAMMING!!! 😂 He picked a problem that worked well for the type of solution he provided. The point of this isn't "how to solve the knapsack problem"

so funny abd simple

Why would you not calvulate a value density for each one, order them from highest to lowest then pack it from the top down? For instance the 1:7 has the highest value per unit of mass, then 2:4, 7:5 and 9:2 last. Pack them in that order until you are just under the limit then reorder and recalculate from there? Eliminate any that are over the remainder, then from there down pair any that are between .5 and 1.0x of the remainder and calculate the density of the pairings, iterate over this process until there are no more under the remainder.

NEAT is such a cool thing!

What's your opinion about using Python for this kind of algorithm? I'm just starting a research (as an undergraduate) on GA and I'm picking up a project were my colleague left off, but is is in Python. It's a very slow language and my research will involve parallelizing some algorithms to make a comparative study.

I think it generally leads to more diversity in the population. Otherwise you might end up with only very similar individuals in the population, which then have very similar ofspring. This is bad because you get "stuck" in a small area of the solution space, while the best solution might be in another area of the solution space entirely. If you only take the best individuals you never select mutations which temporarily give bad solutions but might lead to better ones in the long run. Hope that makes sense.

Tassle So is it basically to avoid the equivalent of inbreeding?

@@gingeh1 You could frame it that way (except that inbreeding in this context doesn't really produce worse results, but can prevent producing better ones)

Knapsack is a problem, not an algorithm. There are loads of algorithms that can approximate an answer to the knapsack problem.

Hopefully, you have access to, and time on, a supercomputer to calculate it all out.

It's Alibaba

Interesting what did it include?

What's DP? I heard my mum mention it to my dad and uncle.

@@TVIDS123 dynamic programming

@@xfxxgj7086 He was joking hahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahaha

I once worked with a developer whose boss had asked him not to use the word "trivial" because it was giving clients the wrong idea.

@@xfxxgj7086 Actually... I think DP in this case is Diploma. The IB DP computer science exam is on genetic algorithms next year.

Try it! ;-)

It's probably pretty easy for a knowledgeable person. With some approximations, of course.

Yes

You might be interested in artificial life, the CS field that aims to emulate life in computers

If you're talking about a RNA virus that makes a bunch of proteins that then need to deliver the RNA payload into new cells to infect, you'll need some way to estimate how well those proteins work. You might need to find a solution to or a way to bypass the "folding problem" which is that a protein with a specific sequence of amino acids in water always folds into the same shape, but predicting the shape it will take out of all possible shapes it could take is very hard. The shape it folds into determines how well the protein works.

1110 is the best, with a value of 16 and a weight of 10. We can't have all 4 pieces (that would be 19 kg), but if we remove the least valuable piece, we are already under 15 kg.

dynamic programming

I think the "solution" is the generalized algorithm - solving this SPECIFIC problem is not really the point.

This type of algorithm is used when there is no obvious alternative - meaning that there is no known 'faster' way, and also if a brute force search is impossible due to the huge number of possible solutions (aka 'combinatorial explosion').

@ambassador - a simple loop that requires an astronomical number of iterations isn't feasible, unless you have an astronomical amount of time. This problem is known as the combinatorial explosion.

Look up pictures of "fan fold paper" and "line printers". Oh, the memories. Nottingham seems to have infinite supplies of this paper. :)

It works well for even more complicated problems, where listing all permutations is not possible. Stuff with many continuous variables. Check out CaryKH's evolution simulator on KZfaq for another example

They're only useful when it's not practical to do a brute force search (i.e., when evaluating every possible permutation would take a very long time).

Remember the last part of the video. Even for 100 boxes, each solution is 100 bits long and as such there are 2^100 solutions to search through. That's already a massive amount of data to search through by brute force. Also consider that the solution space for this problem was discrete and finite, it could be made infinitely big by a very small change in the problem. If you had liquids instead of boxes, you would need to consider taking 0.5 units or pi units or 2.2852 units of liquid. Basically it would be fundamentally impossible to list all solutions.

Usually, knapsack problems are solved with dynamic programming which caches previous computations to reduce the time complexity to polynomial time. Idk how it works with random mutations

It's NP-hard.

Yes, and probably done better than with a GA.

If that's all you're going to do, then you're done on the 1st round. You'd never generate any *new* combinations, so the best solution on the 1st round is the best you'll ever have.

@@jursamaj yea, I implemented a random pivot point for my crossover. I was just curious because he mentions a crossover rate and I was assuming that meant a % chance for crossover to occur.

@@kyleallain5923 Possibly that, or a random point along the length for crossover, which is more like what happens with real genetics. Every chromosome gets at least 1 crossover per reproduction, and can get more.

s/irrelant/irrelevant/ sorry!

In the UK I just search "music lined tractor feed printer paper" or "continuous stationery" - last two batches were bought from a company called Paperstone hth -Sean

@@Computerphile Hah! Just found them, and I think it's wonderful that the paper size is "11 inch x 362mm"!! Get your units sorted out people! (And thank you for the pointer)

But the algorithm isn't looking for complexity…

@@jursamaj i know, its just that if you're looking for complex solutions to problems - this might not be it.

Yep, they're culled. They would be the Darwinistic equivalent of dying before reproducing.

When to stop: Keep track of the overall population average fitness, and if several generations pass without the population fitness improving, call it quits and present the currently fittest solution as the final answer.

8:52 ...

minimize the weight, dont try to fill the knapsack

sorting a set of new (pca) variables, 0.72, 2, 7, 0.22, should give you a preferred order of selected items of [3,2,1,4], then just add up weights, it will be (breadth first search, quaranteed best solution fast, ie, always take the best item you can fit, then skip over if it does not fit, ie, always the best), in order of [3,2,1,4] w=0->1->3->10->19, so this algorithm gives a selection of set [1,2,3], with a weight of 10, which is under 15, but is it the optimum

the first suggested algorithm gives value of 16, not NP complete, at all, mostly radix ratios

try solving go with local focus zones, having a tractable 2^n size, times the total number of same size focus zones (like visual neuron focus zones), so not 2^n in one focus zone, but N*2^n is approximately linear with the number N size of the zones that fit the go game board

pca the other dimensions, down to one sortable number, ie, value against weight and size, ie k-sort-value = value/(weight*size)

It's probably much worse in simple cases like with just weight and value, but I can imagine that if the problem becomes more complex, it will get more and more difficult to solve it with dynamic programming

That would optimise the total value of one haul, but maybe you should make it more complex and take "effort to bring this home or sell it" into it as well. If there is for example cheese or a bucket to be looted next to your house or a vendor that could be worth taking, but if it's a longer trip then that additional effort would not make it worthwhile.

My way of doing it was always to only pick up items with a gold/weight ratio of over 10, which was easy to calculate in my head. Remove the last digit from the value, if it's greater than the weight, keep it. Once I got full, I'd make more room by dropping the items with the lowest value/weight ratio until I could pick up the new item. If I wanted to optimize it completely for value, then I shouldn't have discriminated against ratios of less than 10, but then you spent to much time picking up and dropping things, so I optimized partially for my quality of life haha.

It is a great example. What you have proposed is called a greedy heuristic, and is not guaranteed to provide an optimal solution for the knapsack problem. Knapsack problems (it leads to many applications, think about any decision under capacity or budget constraints) are highly complex and there are no known algorithms or heuristics that are just "the best" to solve all instances of them.

@@lucasgabrielmalheiros5589thank you for the clarification that makes sense, i can see how multiple parameters would make it a lot harder

It's a quick read. I believe the Signal protocol was based on it, or at least inspired by it

C418 - match cut (dna music)

@@noamlima9402 Huh??

@@dannygjk something similar

@@noamlima9402 I have no idea what you mean.

@@dannygjk cognition