1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

(https://swayam.gov.in) (https://swayam.gov.in/nc_details/NPTEL)

[email protected] 

NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Artificial Intelligence Search Methods For Problem Solving (course)

Announcements (announcements) About the Course (preview) Ask a Question (forum) Progress (student/home) Mentor (student/mentor)

Unit 7 - Week 4

Course outline

How does an NPTEL online

Assignment 4
course work? The due date for submitting this assignment has passed. Due on 2020-10-14, 23:59 IST.
As per our records you have not submitted this assignment.
Pre-requisite Assignment
1) Consider the influence graph shown below, it depicts a closed ecosystem. Do not impose any more conditions (from nature) on this graph. Keep it 1 point
Week 0 simple

Week 1

Week 2

Week 3

Week 4

Genetic Algorithms: Survival

of the Fittest (unit?
unit=24&lesson=140)

Genetic Algorithms and SAT

(unit?unit=24&lesson=141)

Genetic Algorithms for the

TSP (unit? Grass has direct influence on Lions
unit=24&lesson=142)
Grass has indirect influence on Lions
Emergent Systems (unit? Bacteria has direct influence on Fungi
unit=24&lesson=143)
Bacteria has indirect influence on Fungi
Ant Colony Optimization Hawk has direct influence on Fungi
(unit?unit=24&lesson=144)
Hawk has only indirect influence on Fungi
Week 4- Feedback : Artificial There is at least one node in the graph that is not (directly or indirectly) influenced by any other node
Intelligence Search Methods
for problem Solving (unit? No, the answer is incorrect.
unit=24&lesson=28)
Score: 0
Accepted Answers:
Lecture Materials (unit? Grass has indirect influence on Lions
unit=24&lesson=175) Bacteria has direct influence on Fungi
Quiz : Assignment 4
Bacteria has indirect influence on Fungi
(assessment?name=195) Hawk has direct influence on Fungi

2) In Week 4, a famous study on creating virtual creatures using genetic algorithms was discussed and the following web resources were listed in 1 point
Week 5
the lecture.

Week 6
    Evolved Virtual Creatures,https://www.karlsims.com/evolved-virtual-creatures.html
(https://www.karlsims.com/evolved-virtual-creatures.html)
Week 7
    Pirouette - Evolved Virtual Creature, https://www.youtube.com/watch?v=GS18h-_h6IM (https://www.youtube.com/watch?
v=GS18h-_h6IM)
Week 8
The fitness vs time (generation number) from the 2nd web resource is reproduced here.
Week 9

Week 10

Week 11

Week 12

DOWNLOAD VIDEOS

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 1/6
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

What can you say about this plot?

the plot is generated from a small population

the fitness function maximizes the net upward movement
there is a general upward trend but often the fitness drops and recovers and improves
at around 1,300th generation (shown by the arrow) the fitness jumps because a different fitness function was used
No, the answer is incorrect.
Score: 0
Accepted Answers:
the plot is generated from a small population
the fitness function maximizes the net upward movement
there is a general upward trend but often the fitness drops and recovers and improves
at around 1,300th generation (shown by the arrow) the fitness jumps because a different fitness function
was used

3) The following articles (freely available) are from the first web resource listed in the previous question. 1 point

    Evolving Virtual Creatures

    K.Sims, Computer Graphics (Siggraph '94 Proceedings), July 1994, pp.15-22.
    https://www.karlsims.com/papers/siggraph94.pdf (https://www.karlsims.com/papers/siggraph94.pdf)

    Evolving 3D Morphology and Behavior by Competition

    K.Sims, Artificial Life IV Proc., ed. by Brooks & Maes, MIT Press, 1994, pp.28-39.
    https://www.karlsims.com/papers/alife94.pdf (https://www.karlsims.com/papers/alife94.pdf)

Three figures from the first article are reproduced here.

What do these figures illustrate?

Virtual creatures that have evolved to jump

Virtual creatures that have evolved to walk
Virtual creatures that have evolved to swim
Model of robots sketched by an artist

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 2/6
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

Prototype of robots designed by an engineer

No, the answer is incorrect.
Score: 0
Accepted Answers:
Virtual creatures that have evolved to jump
Virtual creatures that have evolved to walk
Virtual creatures that have evolved to swim

4) The idea of using population based methods to solve optimization problems 1 point

is only to exploit parallel search like in Iterative Hill Climbing

is to hope that one of the parallel Simulated Annealing searches will find the solution
is to go beyond parallelism and exploit interaction between members of the population
is to exploit the diversity in a population of candidates and try mixing up the candidate solutions
No, the answer is incorrect.
Score: 0
Accepted Answers:
is to go beyond parallelism and exploit interaction between members of the population
is to exploit the diversity in a population of candidates and try mixing up the candidate solutions

5) Which of the following are true? Mark all correct answers 1 point

Genetic Algorithms work with a population of problem solving agents

Genetic Algorithms work with a population of candidate solutions
Ant Colony Optimization works with a population of problem solving agents
Ant Colony Optimization works with a population of candidate solutions
No, the answer is incorrect.
Score: 0
Accepted Answers:
Genetic Algorithms work with a population of candidate solutions
Ant Colony Optimization works with a population of problem solving agents

6) Genetic Algorithms work best when 1 point

there is a large population of diverse candidates

there is a large population of similar candidates
there is a small population of diverse candidates
there is a small population of similar candidates
No, the answer is incorrect.
Score: 0
Accepted Answers:
there is a large population of diverse candidates

7) Darwin’s theory of natural selection can be seen as 1 point

a process of selecting the best leader based on their education

a process of selecting the best leader based on their ability to tell lies
a process to design life forms that evolve and improve over generations
a process where members of a population compete for survival
No, the answer is incorrect.
Score: 0
Accepted Answers:
a process to design life forms that evolve and improve over generations
a process where members of a population compete for survival

8) Which one of the following completes the quote from Paul Valery in the context of Genetic Algorithms? “It takes two to invent anything. The one 1 point
makes up combinations, _________________”

the other creates the permutations

the other chooses
the other sorts the components
the other randomizes them
No, the answer is incorrect.
Score: 0
Accepted Answers:
the other chooses

9) The single point crossover can be used to solve the TSP problem if the representation is 1 point

the path representation

the ordinal representation
the adjacency representation
none of the above
No, the answer is incorrect.
Score: 0
Accepted Answers:
the ordinal representation

10) Conway’s Game of life is 1 point

a video battle game between two persons

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 3/6
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

a video battle game between two teams

an online career counselling site
a cellular automaton
No, the answer is incorrect.
Score: 0
Accepted Answers:
a cellular automaton

11) When Christof Koch said “The most complex object in the known universe” he was referring to 1 point

the Cray supercomputer

the Mars Rover
a formula One car
the human brain
No, the answer is incorrect.
Score: 0
Accepted Answers:
the human brain

12) What is the role an individual ant plays in the Ant Colony Algorithm? 1 point

It conveys the messages from the queen to the soldiers

It constructs a candidate solution using divide and conquer approach
It constructs a candidate solution using a greedy stochastic search approach
It guards the entrance of the ant colony
No, the answer is incorrect.
Score: 0
Accepted Answers:
It constructs a candidate solution using a greedy stochastic search approach

BEGIN GROUP

A tour is shown in the figure, where the edges are bidirectional. Use A,B,C,D,E,F,G,H,I,J as the reference sequence (index sequence) for preparing
ordinal representation and adjacency representation.

13) Which of the following are valid path representations of the tour shown in the figure? 1 point

A,F,E,J,B,G,D,I,C,H,A
A,F,E,J,B,G,D,I,C,H
A,F,E,B,J,D,G,I,C,H
I,C,H,A,F,E,J,B,G,D
I,D,G,B,J,E,F,A,H,C
E,F,A,H,C,I,D,G,B,J
No, the answer is incorrect.
Score: 0
Accepted Answers:
A,F,E,J,B,G,D,I,C,H
I,C,H,A,F,E,J,B,G,D
I,D,G,B,J,E,F,A,H,C
E,F,A,H,C,I,D,G,B,J

14) Which of the following are valid adjacency representations of the tour shown in the figure? 1 point

A,B,C,D,E,F,G,H,I,J
H,J,I,G,F,D,B,C,A,E
F,G,H,I,J,E,D,A,C,B
F,G,H,I,J,A,D,E,C,B
H,J,I,G,F,A,B,C,D,E
None of the above
No, the answer is incorrect.
Score: 0
Accepted Answers:
F,G,H,I,J,E,D,A,C,B
H,J,I,G,F,A,B,C,D,E

15) Question 13 lists many path representations of the tour shown in the figure. Which of the following are the ordinal representations of the valid path 1 point
representations in question 13?

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 4/6
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

1,5,4,1,6,2,2,3,1,1
1,5,4,7,1,3,2,3,1,1
9,3,7,1,4,3,4,1,2,1
9,4,6,2,6,3,3,1,2,1
5,5,1,5,2,4,2,2,1,1
5,5,5,4,2,2,2,1,1,1
No, the answer is incorrect.
Score: 0
Accepted Answers:
1,5,4,7,1,3,2,3,1,1
9,3,7,1,4,3,4,1,2,1
9,4,6,2,6,3,3,1,2,1
5,5,1,5,2,4,2,2,1,1

16) The path representation of two tours are given below. Generate offsprings using Partially Mapped Crossover between P1 and P2 and use locations from
4 to 7 (including 4 and 7) as the mapping segment.

   P1: A,F,E,J,B,G,D,I,C,H
   P2: B,D,G,I,H,C,F,J,E,A

Enter one of the resulting child tours in the textbox. Use path representation (comma separated list of city labels) without extraneous characters like
spaces, period, parenthesis, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) H,F,C,J,B,G,D,I,E,A
(Type: String) A,D,E,I,H,C,F,J,G,B

1 point

17) The path representation of two tours are given below. Generate offsprings using Order Crossover between P1 and P2 and use locations from 4 to 7
(including 4 and 7) as the mapping segment. In the child tour, place the mapping segment in the last part of the tour. For example, C1 =
?,?,?,?,?,?,J,B,G,D

   P1: A,F,E,J,B,G,D,I,C,H
   P2: B,D,G,I,H,C,F,J,E,A

Enter one of the resulting child tours in the textbox. Use path representation (comma separated list of city labels) without extraneous characters like
spaces, period, parenthesis, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) I,H,C,F,E,A,J,B,G,D
(Type: String) A,E,J,B,G,D,I,H,C,F

1 point

18) The path representation of two tours are given below. Generate offsprings using Cycle Crossover between P1 and P2. Inherit odd cycles from one parent
and even cycles from the other parent to create the offsprings.

   P1: A,F,E,J,B,G,D,I,C,H
   P2: B,D,G,I,H,C,F,J,E,A

Enter one of the resulting child tours in the textbox. Use path representation (comma separated list of city labels) without extraneous characters like
spaces, period, parenthesis, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) A,D,E,I,B,G,F,J,C,H
(Type: String) B,F,G,J,H,C,D,I,E,A

1 point

19) The path representation of two tours are given below. Compute the ordinal representations of the parent tours. Use single point (mid point) crossover to
generate offsprings.

   P1: A,F,E,J,B,G,D,I,C,H
   P2: B,D,G,I,H,C,F,J,E,A

Enter one of the resulting child tours in the textbox. Use ordinal representation (comma separated list of numbers) without extraneous characters like
spaces, period, parenthesis, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) 1,5,4,7,1,2,3,3,2,1

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 5/6
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 7 - Week 4

(Type: String) 2,3,5,6,5,3,2,3,1,1

1 point

20) Taking the answers from the previous question, convert the offsprings from ordinal representation to path representation.

Enter one of the resulting child tours in the textbox. Use path representation (comma separated list of city labels) without extraneous characters like
spaces, period, parenthesis, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) A,F,E,J,B,D,H,I,G,C
(Type: String) B,D,G,I,H,E,C,J,A,F

1 point

END GROUP

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=24&assessment=195 6/6