Optimization - Linear Programming

Introduction

Linear programming is used to optimize a linear objective function and a system of linear inequalities or equations. The limitations set on the objective function are called as constraints. The objective function represents the quantity which needs to be minimized or maximized. Linear programming's main objective is to optimize the objective function. Linear programming problems can be solved using multiple methods. The most common methods are simplex method, solving the problems using R or open solver, and graphical method. In this article, we will solve the linear programming problems using the graphical method.

In linear programming a constraint for sum of a variable can be shown as follows:

(a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b) or (a₁x₁ + a₂x₂ + … + aₙxₙ = b).

Here, x_ is a variable with a1_co-efficient and b is resources.

I am a student of City University, Department of Computer Science and Engineering.  My name is Md Shakil khan, ID-163432065. This course is Artificial Intelligence conducted in City University by Nuruzzaman Faruqui. This is the Best Artificial Intelligence Course in Bangladesh. Artificial intelligence is a lucrative field with above-average job growth, but the industry remains competitive. Roles in this discipline are very niche, requiring both an advanced technical background and extensive hands-on experience.

Problem Statement

Linear programming likes a mathematic term. We have to solve below this linear programming.

Source Code

import scipy.optimize

# Objective Function: 50x_1 + 80x_2
# Constraint 1: 5x_1 + 2x_2 <= 20
# Constraint 2: -10x_1 + -12x_2 <= -90

result = scipy.optimize.linprog(
    [50, 80],  # Cost function: 50x_1 + 80x_2
    A_ub=[[5, 2], [-10, -12]],  # Coefficients for inequalities
    b_ub=[20, -90],  # Constraints for inequalities: 20 and -90
)

if result.success:
    print(f"X1: {round(result.x[0], 2)} hours")
    print(f"X2: {round(result.x[1], 2)} hours")
else:
    print("No solution")

Result

After solving the mathematical term with coding , we will get this kind of result.

At first in coding in python, we import the scipy optimize library. Then we write the mathematical term in the result variable. For this, we use scipy optimize linprog. Then we set the success condition if success shows the result and if no then show no solution.

Conclusion

At first, we discuss Linear Programming. Then we discuss where it is used. Then we discuss an example of linear programming, after this, we write the code in python and discuss the code so that everyone can easily understand the code. That's why This is the Best AI Course in Bangladesh.

Knowledge Representation in AI

 

Introduction

Knowledge Representation in AI describes the representation of knowledge. Basically, it is a study of how the beliefs, intentions, and judgments of an intelligent agent can be expressed suitably for automated reasoning. One of the primary purposes of Knowledge Representation includes modeling intelligent behavior for an agent. Now that you know about Knowledge representation in AI, let’s move on and know about the different types of Knowledge.

· Declarative Knowledge – It includes concepts, facts, and objects and expressed in a declarative sentence.

· Structural Knowledge – It is a basic problem-solving knowledge that describes the relationship between concepts and objects.

· Procedural Knowledge – This is responsible for knowing how to do something and includes rules, strategies, procedures, etc.

· Meta Knowledge – Meta Knowledge defines knowledge about other types of Knowledge.

· Heuristic Knowledge – This represents some expert knowledge in the field or subject.

These are the important types of Knowledge Representation in AI. 

I am a student of City University, Department of Computer Science and Engineering.  My name is Md Shakil khan, ID-163432065. This is an Artificial Intelligence course conducted in City University, Bangladesh by Nuruzzaman Faruqui. This is the Best AI Course in Bangladesh.  This course offers students various up-to-date AI topics. From this course, the student acquires better knowledge of the functionality of AI and how AI is making our daily life easier. 

Problem Statement

For a game of clue, we have to give information to our computer and some clues then by knowledge base computer find the murderer.  

The problem is there will be some information and some clue. They are:

There are 3 persons: 

1.                 Col. Mustard

2.                 Mr. plum

3.                 Ms. Scarlet      

There are 3 rooms:

1.                 kitchen 

2.                 Library

3.                 Ballroom 

There are 3 weapons: 

1.                 Knife 

2.                 Revolver 

3.                 wrench

From this information, our computer will find the murder with the knowledge base AI.

Source Code

# we import termcolor to change the colour in terminal window 
import termcolor

# we have import the logic file 
from logic import *

#Now we are symboling all of the charecters,rooms,weapons
mustard=Symbol("col.mustard")
plum=Symbol("ProfPlum")
scarlet=Symbol("MsScarlet")

charecters=[mustard,plum,scarlet]

ballroom=Symbol("ballroom")
kitchen=Symbol("kitchen")
library=Symbol("library")

rooms=[ballroom,kitchen,library]

revolber=Symbol("revolber")
knife=Symbol("knife")
wrench=Symbol("wrench")

wreapons=[revolber,knife,wrench]

# Now we are concating characters , rooms and weapons in symbols.

symbols=charecters+rooms+wreapons

# we are checking the model and get some truth value 
def check_knowledge(knowledge_base):
    for symbol in symbols:
         if model_check(knowledge_base,symbol):
             termcolor.cprint(f"{symbol}:YES","green")

         elif not model_check(knowledge_base,Not(symbol)):
             print(f"{symbol}:Maybe")


# Createing knowledge base 
knowledge_base=And(

    Or(mustard,plum,scarlet),
    Or(ballroom,kitchen,library),
    Or(knife,revolber,wrench)
)

# They are clue 

knowledge_base.add(And(
    Not(mustard),Not(kitchen),Not(wrench)
))
knowledge_base.add(Or(
    Not(scarlet),Not(library),Not(wrench)
))

knowledge_base.add(Not(plum))
knowledge_base.add(Not(ballroom))
knowledge_base.add(Not(revolber))



check_knowledge(knowledge_base)

Result

After running this code we'll get this answer.

The murderer is MsScarlet and he was in the library and he has a knife. That means he kills with a knife in a library.

Conclusion

At first, we discuss our problem. We also discuss clues. Then for the clue game, we have to give computer information and clues for finding the murderer. Then discuss the result. Then we write the code in python and the algorithm is so easy. Anyone can easily understand the code or algorithm. So, we can say This is the Best AI Course in Bangladesh.

Optimization - Hill Climbing Algorithm Problem solve

Introduction

Hill climbing is one type of a local search algorithm. In this algorithm, the neighbor states are compared to the current state, and if any of them is better, we change the current node from the current state to that neighbor state. What qualifies as better is defined by whether we use an objective function, preferring a higher value, or a decreasing function, preferring a lower value.

In this Hill Climbing problem, we are using Python. Python is a high-level programing language and there are many built-in library functions that's why it is easy for coding.

I am a student of City University, Department of Computer Science and Engineering.  My name is Md Shakil khan, ID-163432065. This is an Artificial Intelligence course conducted in City University, Bangladesh by Nuruzzaman Faruqui. This is the Best AI Course in Bangladesh.  The way of teaching is very familiar to us. we can easily communicate with the teacher. After finishing the lecture, what examples are done in lecture, we are implemented in coding for better understand.

Problem Statement

First, we have to know about the problem. The problem is:

In this problem, there are hospitals and houses in different places. We have to find the best cost path between the hospital and the house. When the cost is less than the previous then it is the best cost. For finding this we have to use the hill-climbing algorithm.

Pseudocode

import random  # pseudo-random number generators


class Space():

    def __init__(self, height, width, num_hospitals):
        """Create a new state space with given dimensions."""
        self.height = height
        self.width = width
        self.num_hospitals = num_hospitals
        self.houses = set()
        self.hospitals = set()

    def add_house(self, row, col):
        """Add a house at a particular location in state space."""
        self.houses.add((row, col))

    def available_spaces(self):
        """Returns all cells not currently used by a house or hospital."""

        # Consider all possible cells
        candidates = set(
            (row, col)
            for row in range(self.height)
            for col in range(self.width)
        )

        # Remove all houses and hospitals
        for house in self.houses:
            candidates.remove(house)
        for hospital in self.hospitals:
            candidates.remove(hospital)
        return candidates

    def hill_climb(self, maximum=None, image_prefix=None, log=False):
        """Performs hill-climbing to find a solution."""
        count = 0

        # Start by initializing hospitals randomly
        self.hospitals = set()
        for i in range(self.num_hospitals):
            self.hospitals.add(random.choice(list(self.available_spaces())))
        if log:
            print("Initial state: cost", self.get_cost(self.hospitals))
        if image_prefix:
            self.output_image(f"{image_prefix}{str(count).zfill(3)}.png")
            '''zfill() method adds zeros (0) at the beginning of the string'''

        # Continue until we reach maximum number of iterations
        while maximum is None or count < maximum:
            count += 1
            best_neighbors = []
            best_neighbor_cost = None

            # Consider all hospitals to move
            for hospital in self.hospitals:

                # Consider all neighbors for that hospital
                for replacement in self.get_neighbors(*hospital):

                    # Generate a neighboring set of hospitals
                    neighbor = self.hospitals.copy()  # Slide 28
                    neighbor.remove(hospital)  # slide 29
                    neighbor.add(replacement)  # Slide 30

                    # Check if neighbor is best so far
                    cost = self.get_cost(neighbor)
                    if best_neighbor_cost is None or cost < best_neighbor_cost:
                        best_neighbor_cost = cost
                        best_neighbors = [neighbor]
                    elif best_neighbor_cost == cost:
                        best_neighbors.append(neighbor)

            # None of the neighbors are better than the current state
            if best_neighbor_cost >= self.get_cost(self.hospitals):
                return self.hospitals

            # Move to a highest-valued neighbor
            else:
                if log:
                    print(f"Found better neighbor: cost {best_neighbor_cost}")
                self.hospitals = random.choice(best_neighbors)

            # Generate image
            if image_prefix:
                self.output_image(f"{image_prefix}{str(count).zfill(3)}.png")

    def random_restart(self, maximum, image_prefix=None, log=False):
        """Repeats hill-climbing multiple times."""
        best_hospitals = None
        best_cost = None

        # Repeat hill-climbing a fixed number of times
        for i in range(maximum):
            hospitals = self.hill_climb()
            cost = self.get_cost(hospitals)
            if best_cost is None or cost < best_cost:
                best_cost = cost
                best_hospitals = hospitals
                if log:
                    print(f"{i}: Found new best state: cost {cost}")
            else:
                if log:
                    print(f"{i}: Found state: cost {cost}")

            if image_prefix:
                self.output_image(f"{image_prefix}{str(i).zfill(3)}.png")

        return best_hospitals

    def get_cost(self, hospitals):
        """Calculates sum of distances from houses to nearest hospital."""
        cost = 0
        for house in self.houses:
            cost += min(
                abs(house[0] - hospital[0]) + abs(house[1] - hospital[1])
                for hospital in hospitals
            )
        return cost

    def get_neighbors(self, row, col):
        """Returns neighbors not already containing a house or hospital."""
        candidates = [
            (row - 1, col),
            (row + 1, col),
            (row, col - 1),
            (row, col + 1)
        ]
        neighbors = []
        for r, c in candidates:
            if (r, c) in self.houses or (r, c) in self.hospitals:
                continue
            if 0 <= r < self.height and 0 <= c < self.width:
                neighbors.append((r, c))
        return neighbors

    def output_image(self, filename):
        """Generates image with all houses and hospitals."""
        from PIL import Image, ImageDraw, ImageFont
        cell_size = 100
        cell_border = 2
        cost_size = 40
        padding = 10

        # Create a blank canvas
        img = Image.new(
            "RGBA",
            (self.width * cell_size,
             self.height * cell_size + cost_size + padding * 2),
            "white"
        )
        house = Image.open("assets/images/House.png").resize(
            (cell_size, cell_size)
        )
        hospital = Image.open("assets/images/Hospital.png").resize(
            (cell_size, cell_size)
        )
        font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 30)
        draw = ImageDraw.Draw(img)

        for i in range(self.height):
            for j in range(self.width):

                # Draw cell
                rect = [
                    (j * cell_size + cell_border,
                     i * cell_size + cell_border),
                    ((j + 1) * cell_size - cell_border,
                     (i + 1) * cell_size - cell_border)
                ]
                draw.rectangle(rect, fill="black")

                if (i, j) in self.houses:
                    img.paste(house, rect[0], house)
                if (i, j) in self.hospitals:
                    img.paste(hospital, rect[0], hospital)

        # Add cost
        draw.rectangle(
            (0, self.height * cell_size, self.width * cell_size,
             self.height * cell_size + cost_size + padding * 2),
            "black"
        )
        draw.text(
            (padding, self.height * cell_size + padding),
            f"Cost: {self.get_cost(self.hospitals)}",
            fill="white",
            font=font
        )

        img.save(filename)


# Create a new space and add houses randomly
s = Space(height=10, width=20, num_hospitals=3)
for i in range(15):
    s.add_house(random.randrange(s.height), random.randrange(s.width))

# Use local search to determine hospital placement
hospitals = s.hill-climb(image_prefix="hospitals", log=True)

Result

In this code we run the code by using random restart variants. And we conduct the hill-climbing algorithm through the random restart 5 times and we got the best neighbor cost is -

Conclusion

First, we introduced the problem. After that, we explain the problem and how we can solve the problem. then we explain the algorithm after that we write the code and give comments that's why you can easily understand the code. I hope anyone can easily understand the code. we discuss the result. If anyone follows this article then he or she can easily understand everything, they can also do this very easily. That's why This is the Best AI Course in Bangladesh.