Javascript

Quick intro to Genetic algorithms (with a JavaScript example)

Oct 31, 2019

6 min read

The purpose of this article is to give the reader a quick insight into what genetic algorithms are, and how they work.

In short: What are genetic algorithms?

Genetic algorithms are a metaheuristic inspired by Charles Darwin's theory of natural selection. They replicate the operations: mutation, crossover and selection. These features make them suitable for use in optimization problems. Because of this, they find applications in a lot of disciplines like chemistry, climatology, robotics, gaming, etc. They are part of evolutionary computation.

The example problem

Before implementing the algorithm, let's take a look of the problem we are going to solve.

You might have heard about the infinite monkey theorem which states that, given an infinite amount of time, a monkey will almost certainly type logical, meaningful text while randomly pressing the keys on a keyboard. Of course, the lifetime of a monkey will probably not be long enough for this to happen. Still, the chances are greater than zero. Very close to zero, but not zero. Anyway, let's stick to the metaphor.

Another way we can imagine this: imagine we have a device that produces random strings. At some point in the future, regardless how long it takes, it will output our desired text.

The purpose of the genetic algorithm we are going to develop is to find an optimal way to achieve the result we are looking for rather than brute forcing it (which will inevitably take a ludicrous amount of time).

This problem is widely used as an example for GA, so for the sake of consistency and simplicity, we will stick to it.

Parts of GA

We already mentioned some of the operations involved in the process. Let's break down the different steps involved in the GA:

Initializing the population - This is the first step. We will pick a set of members with different traits (or genes). The key here is to have a big enough variety in order to evolve to the target for which we are aiming.
Selection - The process of selecting those members of our population who are fit enough to be reproduced. This happens by predetermined criteria.
Reproduction - After we select the fittest members from our current generation, we will perform a crossover -- mixing their traits/genes. Optionally, we will mutate the newly produced members by some random factor. That way, we will further support the variety in our population.
Repeat 2 and 3 - Simply said -- we will perform selection, crossover and mutation for every new generation until the population evolves to such an extent that we have the desired candidate.

Implementation

Okay, before we start with the algorithm, let's first introduce two utility functions that we are going to use throughout the example. The first one will be used for generating a random integer value in a provided interval, and the second -- generating a letter from a-z:

// Src: MDN
function random(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);

  // The maximum is exclusive and the minimum is inclusive
  return Math.floor(Math.random() * (max - min)) + min;
}

function generateLetter() {
  const code = random(97, 123); // ASCII char codes
  return String.fromCharCode(code);
}

Now that we have our utils ready, we'll start with the first step of the genetic algorithms, which is:

Initializing the population

Let's introduce our population member or the monkey that we referenced previously. It will be represented by an object called Member which contains an array with the pressed keys, and the target string. The constructor will generate a set of randomly pressed keys:

class Member {
  constructor(target) {
    this.target = target;
    this.keys = [];

    for (let i = 0; i < target.length; i += 1) {
      this.keys[i] = generateLetter();
    }
  }
}

For example, new Member('qwerty') can result in a member who pressed a, b, c, d, e, f or y, a, w, r, t, w.

Next, after we have our member created, let's move to the population object, which will keep the set of members we want to evolve:

class Population {
  constructor(size, target) {
    size = size || 1;
    this.members = [];

    for (let i = 0; i < size; i += 1) {
      this.members.push(new Member(target));
    }
  }
}

The Population should accept size and target (target string). In the constructor, we are going to generate size members all with randomly generated words, but with equal length.

This should be enough to create a diverse initial population!

Selection

It's time for us to add some methods to the classes we created. We will start with the Member. Do you remember that we had to develop some criteria based on how we determine the fitness of our members? This is exactly what we are going to do by introducing the fitness method.

Let me elaborate:

class Member {
  // ...

  fitness() {
    let match = 0;

    for (let i = 0; i < this.keys.length; i += 1) {
      if (this.keys[i] === this.target[i]) {
        match += 1;
      }
    }

    return match / this.target.length;
  }
}

As you can see, what we are attempting to do is to find how many of the randomly pressed keys (by a member) match the letters in our target string. The more, the better! Since we want to have a coefficient as an output, we will divide the matches by the length of the target.

Going back to our Population class, we will implement the actual selection operation. Logically, we would like to have the fitness calculated to every member of the population.

Based on that value, we want to increase the chances of the fittest members being selected, and respectively, decrease the chances of selection for the least fit candidates for the new generation. This can happen by adding an additional array called the mating pool. In it, we will add every member, multiplied by its-fitness-coefficient. To grasp this concept, let's take a look at this example:

Member1 (fitness = 4)
Member2 (fitness = 2)
Member3 (fitness = 1)

== Output ==

MatingPool = [
  Member1, Member1, Member1, Member1,
  Member2, Member2,
  Member3
]

At this point, you should be able to guess the idea behind this approach -- to increase the chances of the fittest members being randomly selected. Note that there are different ways for building your mating pool distribution.

And the code:

class Population {
  // ...

  _selectMembersForMating() {
    const matingPool = [];

    this.members.forEach((m) => {
      // The fitter it is, the more often it will be present in the mating pool
      // i.e. increasing the chances of selection
      // If fitness == 0, add just one member
      const f = Math.floor(m.fitness() * 100) || 1;

      for (let i = 0; i < f; i += 1) {
        matingPool.push(m);
      }
    });

    return matingPool;
  }
}

Now that we have readied our selection process, it is time to reproduce!

Reproduction

In this section of the implementation, we will focus on the crossover, and mutation operations. This will require further extending of our Member class. I will start by creating the crossover method. Its role is to combine/mix the traits, genes, or in our case, keys, of two parents randomly selected from the mating pool. The output child might contain only keys from parent A or keys from parent B, but in most cases, it will contain keys from both the parents. This happens by selecting a random index from the array that contains them:

class Member {
  // ...

  crossover(partner) {
    const { length } = this.target;
    const child = new Member(this.target);
    const midpoint = random(0, length);

    for (let i = 0; i < length; i += 1) {
      if (i > midpoint) {
        child.keys[i] = this.keys[i];
      } else {
        child.keys[i] = partner.keys[i];
      }
    }

    return child;
  }
}

Since we are working with the Member, let's add our last method to it. This is the mutate method. Its purpose is to give some uniqueness, and randomness, to the newly created child. It's worth mentioning that the mutation is not something that every genetic algorithm incorporates. That's why we will use a rate which will make the process controlled:

class Member {
  // ...

  mutate(mutationRate) {
    for (let i = 0; i < this.keys.length; i += 1) {
      // If below predefined mutation rate,
      // generate a new random letter on this position.
      if (Math.random() < mutationRate) {
        this.keys[i] = generateLetter();
      }
    }
  }
}

// We will also have to update the Population constructor
class Population {
  constructor(size, target, mutationRate) {
    size = size || 1;
    this.members = [];
    this.mutationRate = mutationRate // <== New property

    // ...
  }

  // ...
}

It's time to tie these two in our Population class. Previously, we added the _selectMembersForMating. Let's make use of it:

class Population {
  // ...

  _reproduce(matingPool) {
    for (let i = 0; i < this.members.length; i += 1) {
      // Pick 2 random members/parents from the mating pool
      const parentA = matingPool[random(0, matingPool.length)];
      const parentB = matingPool[random(0, matingPool.length)];

      // Perform crossover
      const child = parentA.crossover(parentB);

      // Perform mutation
      child.mutate(this.mutationRate);

      this.members[i] = child;
    }
  }
}

Here, we only pick 2 random parents. Then, we perform the crossover. After that comes the mutation. And then finally, we replace the member with the new child. That's it!

We are almost done. For the purposes of this demo, we are going to add control over the number of generations (or iterations) that we want to have. That way, we can closely monitor how our population changes over time. In a real world scenario, we would like to create new generations until we reach our final goal or target. Anyway, let's add the final evolve method to the Population class for that goal:

class Population {
  // ...

  evolve(generations) {
    for (let i = 0; i < generations; i += 1) {
      const pool = this._selectMembersForMating();
      this._reproduce(pool);
    }
  }
}

In the end, we will add a helper function that will make the running process a bit easier for us:

function generate(populationSize, target, mutationRate, generations) {
  // Create a population and evolve for N generations
  const population = new Population(populationSize, target, mutationRate);
  population.evolve(generations);

  // Get the typed words from all members, and find if someone was able to type the target
  const membersKeys = population.members.map((m) => m.keys.join(''));
  const perfectCandidatesNum = membersKeys.filter((w) => w === target);

  // Print the results
  console.log(membersKeys);
  console.log(`${perfectCandidatesNum ? perfectCandidatesNum.length : 0} member(s) typed "${target}"`);
}

generate(20, 'hit', 0.05, 5);

Running this, we will create a population of 20 members whose target is to type "hit". We'll execute it for 5 generations with a mutation rate of 5%.

Note: Keep in mind that, for our demo, the target string must contain only lowercase a-z letters.

Results

Having this particular population evolve for 5 generations will probably end up with 0 members who typed "hit". However, making that number 20 might land us a good candidate:

  5 Generations  |  20 Generations
-----------------|------------------
       ...       |        ...
                 |
      'gio'      |       'fit'
      'yix'      |       'hrt'
      'gio'      |    >> 'hit' <<
      'kbo'      |       'hiy'

Online demo

You can find the full source code on GitHub

If you want to dig more into genetic algorithms ...

Since the article only lightly touches on what genetic algorithms are, I highly recommend you check out The Nature of Code by Daniel Shiffman (from which this text was based on). It is a great resource for those who want a deeper insight.

This Dot is a consultancy dedicated to guiding companies through their modernization and digital transformation journeys. Specializing in replatforming, modernizing, and launching new initiatives, we stand out by taking true ownership of your engineering projects.

We love helping teams with projects that have missed their deadlines or helping keep your strategic digital initiatives on course. Check out our case studies and our clients that trust us with their engineering.

Using HttpClient in Modern Angular Applications

Introduction With all the wonderful treats that the Angular team has given us during the recent "renaissance" era, many new developers are joining in on the fun. And one of the challenges they'll face at some point is how to call an API from your Angular application properly. Unfortunately, while searching for a guide on how to do this, they might stumble upon a lot of outdated information. Hence, this article should serve as a reliable guide on how to use the HttpClient in Angular >= 17. The Setup To make an HTTP request in Angular, you can take advantage of the HttpClient provided by the @angular/common/http package. To use it, you'll need to provide it. Here's how you can do that for the whole application using the bootstrapApplication function from @angular/platform-browser: ` With that, you should be good to go. You can now inject the HttpClient into any service or component in your application. Using HttpClient in Services Let's take a common example: You have a database object, say a Movie, and you want to implement CRUD operations on it. Typically, you'll want to create a service that provides methods for these operations. Let's call this service MovieService and create a skeleton for it with a method for getting all movies. ` Implementing the Method using HttpClient Let's assume we have a GraphQL API for our movies. We can implement our getAllMovies using HttpClient to make a request to fetch all movies. First, we will need to define a new type to represent the response from the API. This is especially important when you are using GraphQL, which may return a specific structure, such as: ` When working with a real API, you'll likely use some code generator to generate the types for the response from the GraphQL schema. But for the sake of this example, we'll create an interface to represent the response manually: ` Now, we can implement the getAllMovies method using HttpClient: ` > Note: The post method is used here because we are sending a request body. If you are making a GET request (e.g. to a REST API), you can use the get method instead. The getAllMovies method returns an Observable of MoviesListResponse. In this example, I have typed it explicitly to make it obvious at first glance, but you could also omit the type annotation, and TypeScript should infer it. > Note: While I'm excited about signals as much as the next guy, making HTTP requests is one of the typical async operations for which RxJS Observables are a perfect fit, making a great argument for RxJS still having a solid place in Angular alongside signals. Using the Service in a Component Now that we have our MovieService set up, we can use it as a component to fetch and display all movies. But first, let's create a Movie interface to represent the structure of a movie. Trust me, this will prevent many potential headaches down the line. Although using any at the beginning and implementing the types later is a valid approach in some cases, using data fetched from an API without validating the type will inevitably lead to bugs that are difficult to solve. ` Now, we can start implementing our standalone MoviesComponent: ` In this component, we are calling the getAllMovies method from the MovieService in the constructor to fetch all movies and assign them to the movies property which we will use to display the movies in the template. ` In this case, placing our code inside the constructor is safe because it doesn’t depend on any @Input(). If it were, our code would fail because the inputs aren’t initialized at time of instantiation. That's why it is sometimes recommended to place logic in ngOnInit instead. You could also put this call in an arbitrary method that is called e.g. on a button click. Another way to handle the subscription is to use the async pipe in the template. This way, Angular will automatically subscribe and unsubscribe from the observable for you and you won't have to assign the response to a property in the component. Due to the structure of the returned data, however, we'll need to use the RxJS map operator to extract the movies from the response. ` > Note using the pipe method to chain the map operator to the observable returned by getAllMovies. This is a common pattern when working with RxJS observables introduced in RxJs 5.5. If you see code that uses the map operator directly on the observable and wonder why it isn't working for you, it's likely using an older version of RxJS. Now, we can simply apply the async pipe in the template to subscribe to the observable and display the movies: ` Conclusion HttpClient in Angular is pretty straightforward, but with all the changes to RxJS and Angular in the past few years, it can pose a significant challenge if you're not super-experienced with those technologies and stumble upon outdated resources. Following this article, you should hopefully be able to implement your service using HttpClient to make requests to an API in your modern Angular application and avoid the struggle of copying outdated code snippets....

Mar 27, 2024

4 mins

AngularJavaScript

Maximizing Routing Flexibility with Next.js Parallel and Intercepting Routes

Maximizing Routing Flexibility with Next.js Parallel and Intercepting Routes Introduction: Next.js, a powerful React framework, offers two essential features - Parallel Routes and Intercepting Routes - that enable developers to create highly dynamic and seamless user experiences in their applications. In this blog post, we will explore both Parallel Routes and Intercepting Routes, highlighting their functionalities, use cases, and how they can be combined to enhance application routing. What are Parallel Routes? Parallel Routes in Next.js allow the rendering of multiple pages within a shared layout. Rather than navigating to a completely separate page, Parallel Routes enable the simultaneous rendering of different pages based on certain conditions such as user roles or tab navigation. By leveraging named slots, defined using the @folder convention, multiple pages can be seamlessly integrated into a single layout, enhancing user experience and reducing code duplication. How to Use Parallel Routes: To utilize Parallel Routes in Next.js, you must define named slots for the desired pages within your application's folder structure. These slots are then passed as props to a shared parent layout component. For example, consider a social networking application where two pages, feed and notifications, must be rendered within a common layout. You can define Parallel Routes using the following structure: ` The layout component in app/layout.js will accept the @feed and @notifications slots as props and render them alongside the children prop. Here's an example of the layout component: ` It's important to note that slots do not affect the URL structure and are not considered route segments. This means the URL would be /mypage/@feed/views for a route like /mypage/views since @feed is a slot. Also, to prevent the application from rendering nothing or throwing an error, we could use the default.tsx file: ` In this example, the default.tsx file specifies the default content (or fallback) to render when none of the named slots match the current route. It acts as a catch-all for routes without a corresponding slot. Some Use Cases: *Conditional Routes:* Parallel Routes can conditionally render routes based on certain conditions, such as user roles. For example, you can render a different dashboard page for admins and users. This can be achieved by creating a layout component specific to the dashboard and checking the user role to determine which slot to render. *Tab Groups:* You can utilize Parallel Routes to create tabbed navigation within a section. This is especially useful for analytics or multi-page views. Adding a layout inside a slot allows users to navigate between different pages within that slot independently. *Loading and Error UI:* Parallel Routes can be independently streamed, allowing you to define custom error and loading states for each route. This enables better control over the user experience by providing distinct feedback for different app sections. *Modals:* Parallel Routes can be combined with Intercepting Routes to create modals with shareable URLs, preserved context on refresh, and customized navigation behavior. By intercepting certain routes and rendering them within a modal component, you can create a seamless modal experience. Understanding Intercepting Routes: Intercepting Routes in Next.js allows you to load content from another route within the current layout without changing the URL or refreshing the page. Using the (..) Convention: Intercepting routes are defined using the (..) convention, which is similar to the relative path convention ../ but for route segments. The convention allows for matching segments on the same level (.), one level above (..), two levels above (..)(..), or from the root app directory (...). For example, to intercept the photo segment from within the feed segment, you can create a (..)photo directory. Integrating Intercepting Routes with Parallel Routes - Modals: One powerful use case for Intercepting Routes is creating modals, which can be combined with Parallel Routes to solve common challenges such as making the modal content shareable through a URL, preserving context on page refresh, and handling backward and forward navigation. Let's make an example: ` Our folder structure will be: In this example, when a user clicks on a photo within the /gallery page, the route /photo/:photoId will be intercepted and rendered within the (..)photo directory, overlaying the gallery content. This means that the photo route is only one segment level higher despite being two file-system levels higher. In the example above, the path to the photo segment can use the (..) matcher since @modal is a slot and not a segment. Common Use Cases - Beyond Modals: Intercepting Routes can also be utilized in other scenarios. Some examples include opening a login modal in a top navbar while having a dedicated /login page, or opening a shopping cart in a side modal for better accessibility or creating wizards or multi-step forms within a single page. The possibilities are endless. Conclusion Next.js Parallel and Intercepting Routes offer powerful methods for enhancing the routing capabilities of your applications. With Parallel Routes, multiple pages can be seamlessly integrated within a shared layout, simplifying navigation and enhancing user experience. By incorporating Intercepting Routes, you can create dynamic overlays like modals, enabling content from different routes to be displayed within the current layout. By leveraging these features, you can unlock exciting possibilities and take your Next.js applications to new heights of user engagement....

Apr 5, 2024

3 mins

NextJSJavaScript

End-to-end type-safety with JSON Schema

End-to-end type-safety with JSON Schema I recently wrote an introduction to JSON Schema post. If you’re unfamiliar with it, check out the post, but TLDR: It’s a schema specification that can be used to define the input and output data for your JSON API. In my post, I highlight many fantastic benefits you can reap from defining schemas for your JSON API. One of the more interesting things you can achieve with your schemas is end-to-end type safety from your backend API to your client application(s). In this post, we will explore how this can be accomplished slightly deeper. Overview The basic idea of what we want to achieve is: * a JSON API server that validates input and output data using JSON Schema * The JSON Schema definitions that our API uses transformed into TypeScript types With those pieces in place, we can achieve type safety on our API server and the consuming client application. The server side is pretty straightforward if you’re using a server like Fastify with already enabled JSON Schema support. This post will focus on the concepts more than the actual implementation details though. Here’s a simple diagram illustrating the high-level concept: We can share the schema and type declaration between the client and server. In that case, we can make a request to an endpoint where we know its type and schema, and assuming the server validates the data against the schema before sending it back to the client, our client can be confident about the type of the response data. Marrying JSON Schema and TypeScript There are a couple of different ways to accomplish this: * Generating types from schema definitions using code generation tools * Creating TypeBox definitions that can infer TypeScript types and be compiled to JSON Schema I recommend considering both and figuring out which would better fit your application and workflows. Like anything else, each has its own set of trade-offs. In my experience, I’ve found TypeBox to be the most compelling if you want to go deep with this pattern. Code generation A couple of different packages are available for generating TS types from JSON Schema definitions. * https://github.com/bcherny/json-schema-to-typescript * https://github.com/vega/ts-json-schema-generator They are CLI tools that you can provide a glob path to where your schema files are located and will generate TS declaration files to a specified output path. You can set up an npm hook or a similar type of script that will generate types for your development environment. TypeBox TypeBox is a JSON Schema type builder. With this approach, instead of json files, we define schemas in code using the TypeBox API. The TypeBox definitions infer to TypeScript types directly, which eliminates the code generation step described above. Here’s a simple example from the documentation of a JSON Schema definition declared with TypeBox: ` This can then be inferred as a TypeScript type: ` Aside from schemas and types, TypeBox can do a lot more to help us on our type-safety journey. We will explore it a bit more in upcoming sections. Sharing schemas between client and server applications Sharing our JSON Schema between our server and client app is the main requirement for end-to-end type-safety. There are a couple of different ways to accomplish this, but the simplest would be to set up our codebase as a monorepo that contains both the server and client app. Some popular options for TypeScript monorepos are: PNPM, Turborepo, and NX. If a monorepo is not an option, you can publish your schema and types as a package that can be installed in both projects. However, this setup would require a lot more maintenance work. Ultimately, as long as you can import your schemas and types from the client and server app, you are in good shape. Server-to-client validation and type-safety For the sake of simplicity, let's focus on data flowing from the server to the client for now. Generally speaking, the concepts also apply in reverse, as long as your JSON API server validates your inputs and outputs. We’ll look at the most basic version of having strongly typed data on the client from a request to our server. Type-safe client requests In our server application, if we validate the /users endpoint with a shared schema - on the client side, when we make the request to the endpoint, we know that the response data is validated using the user schema. As long as we are confident of this fact, we can use the generated type from that schema as the return type on our client fetch call. Here’s some pseudocode: ` Our server endpoint would look something like this: ` You could get creative and build out a map that defines all of your endpoints, their metadata, and schemas, and use the map to define your server endpoints and create an API client. Transforming data over the wire Everything looks stellar, but we can still take our efforts a bit further. To this point, we are still limited to serialized JSON data. If we have a created_at field (number or ISO string) tied to our user, and we want it to be a Date object when we get a hold of it on the client side - additional work and consideration are required. There are some different strategies out there for deserializing JSON data. The great thing about having shared schemas between our client and server is that we can encode our type information in the schema without sending additional metadata from our server to the client. Using format to declare type data In my initial JSON Schema blog post, I touched on the format field of the specification. In our schema, if the actual type of our date is a string in ISO8601 format, we can declare our format to be "date-time". We can use this information on the client to transform the field into a proper Date object. ` Transforming serialized JSON Data This can be a little bit tricky; again, there are many ways to accomplish it. To demonstrate the concept, we’ll use TypeBox to define our schemas as discussed above. TypeBox provides a Transform type that you can use to declare, encode, and decode methods for your schema definition. ` It even provides helpers to statically generate the decoded and encoded types for your schema ` If you declare your decode and encode functions for your schemas, you can then use the TypeBox API to handle decoding the serialized values returned from your JSON API. Here’s what the concept looks like in practice fetching a user from our API: ` Nice. You could use a validation library like Zod to achieve a similar result but here we aren’t actually doing any validation on our client side. That happened on the server. We just know the types based on the schema since both ends share them. On the client, we are just transforming our serialized JSON into what we want it to be in our client application. Summary There are a lot of pieces in play to accomplish end-to-end type safety. With the help of JSON Schema and TypeBox though, it feels like light work for a semi-roll-your-own type of solution. Another great thing about it is that it’s flexible and based on pretty core concepts like a JSON API paired with a TypeScript-based client application. The number of benefits that you can reap from defining JSON Schemas for your APIs is really great. If you’re like me and wanna keep it simple by avoiding GraphQL or other similar tools, this is a great approach....

Apr 17, 2024

6 mins

JSONTypeScript

How to Go from Software Engineer to AI Engineer with Shawn Wang

Shawn Wang discusses AI engineering’s potential impact on the software development labor market and developer experience. With the rise of artificial intelligence technologies, there is an increasing demand for professionals who can bridge the gap between AI and software engineering, and engineers are looking around for guidance on how to best learn AI. Shawn emphasizes the importance of acquiring core knowledge and skills in AI engineering, highlighting the need for a systematic approach to education and development. He envisions a future where AI engineering becomes a recognized profession, with specialized training programs and certifications. He further talks about mental models for approaching AI literacy, and skill building. Shawn also discusses the use of advanced AI technology in software development. He showcases tools like GPT Vision, which can automate tasks and generate code efficiently. While acknowledging the potential of AI in enhancing productivity, Shawn emphasizes the need to leverage AI tools to augment human capabilities rather than replace them. Download this episode here....

Apr 17, 2024

1 min

Artificial IntelligenceEngineering Leadership

Quick intro to Genetic algorithms (with a JavaScript example)

In short: What are genetic algorithms?

The example problem

Parts of GA

Implementation

Initializing the population

Selection

Reproduction

Results

If you want to dig more into genetic algorithms ...

You might also like

Using HttpClient in Modern Angular Applications

Maximizing Routing Flexibility with Next.js Parallel and Intercepting Routes

End-to-end type-safety with JSON Schema

How to Go from Software Engineer to AI Engineer with Shawn Wang

You might also like

Using HttpClient in Modern Angular Applications

Maximizing Routing Flexibility with Next.js Parallel and Intercepting Routes

End-to-end type-safety with JSON Schema

How to Go from Software Engineer to AI Engineer with Shawn Wang