Map elites 选择

此文件是 TPOT 库的一部分。

TPOT 当前版本由 Cedars-Sinai 开发人员开发：- Pedro Henrique Ribeiro (https://github.com/perib, https://www.linkedin.com/in/pedro-ribeiro/) - Anil Saini (anil.saini@cshs.org) - Jose Hernandez (jgh9094@gmail.com) - Jay Moran (jay.moran@cshs.org) - Nicholas Matsumoto (nicholas.matsumoto@cshs.org) - Hyunjun Choi (hyunjun.choi@cshs.org) - Gabriel Ketron (gabriel.ketron@cshs.org) - Miguel E. Hernandez (miguel.e.hernandez@cshs.org) - Jason Moore (moorejh28@gmail.com)

TPOT 的原始版本主要由宾夕法尼亚大学开发人员开发：- Randal S. Olson (rso@randalolson.com) - Weixuan Fu (weixuanf@upenn.edu) - Daniel Angell (dpa34@drexel.edu) - Jason Moore (moorejh28@gmail.com) - 以及许多其他慷慨的开源贡献者

TPOT 是自由软件：您可以根据自由软件基金会发布的 GNU 宽通用公共许可证的条款（版本 3 或您选择的任何更高版本）重新分发和/或修改它。

分发 TPOT 是希望它会有用，但没有任何担保；不包括对适销性或特定用途适用性的默示担保。有关更多详细信息，请参阅 GNU 宽通用公共许可证。

您应该已收到 TPOT 的 GNU 宽通用公共许可证副本。如果没有，请参阅 https://gnu.ac.cn/licenses/。

create_nd_matrix(matrix, grid_steps=None, bins=None)

创建一个 N 维矩阵，其中包含每个单元格的最高分数

参数

名称	类型	描述	默认值
matrix	ndarray	分数矩阵，其中第一列是分数，其余列是 map-elites 算法的特征。	必需
grid_steps	int	用于自动为每个特征创建 bin 阈值的步数。默认值为 None。	None
bins	list	一个列表的列表，其中包含每个特征（分数除外）的 bin 边缘。默认值为 None。	None

返回值

类型	描述
ndarray	一个 N 维矩阵，其中包含每个单元格的最高分数以及具有该分数的个体的索引。单元格中的值是一个字典，其中包含键“score”和“idx”，分别表示个体的分数和索引。

源代码位于 tpot/selectors/map_elites_selection.py

def create_nd_matrix(matrix, grid_steps=None, bins=None):
    """
    Create an n-dimensional matrix with the highest score for each cell

    Parameters
    ----------
    matrix : np.ndarray
        The score matrix, where the first column is the score and the rest are the features for the map-elites algorithm.
    grid_steps : int, optional
        The number of steps to use for each feature to automatically create the bin thresholds. The default is None.
    bins : list, optional
        A list of lists containing the bin edges for each feature (other than the score). The default is None.

    Returns
    -------
    np.ndarray
        An n-dimensional matrix with the highest score for each cell and the index of the individual with that score.
        The value in the cell is a dictionary with the keys "score" and "idx" containing the score and index of the individual respectively.
    """
    if grid_steps is not None and bins is not None:
        raise ValueError("Either grid_steps or bins must be provided but not both")

    # Extract scores and features
    scores = matrix[:, 0]
    features = matrix[:, 1:]

    # Determine the min and max of each feature
    min_vals = np.min(features, axis=0)
    max_vals = np.max(features, axis=0)

    # Create bins for each feature
    if bins is None:
        bins = [np.linspace(min_vals[i], max_vals[i], grid_steps) for i in range(len(min_vals))]

    # Initialize n-dimensional matrix with negative infinity
    nd_matrix = np.full([len(b)+1 for b in bins], {"score": -np.inf, "idx": None})
    # Fill in each cell with the highest score for that cell
    for idx, (score, feature) in enumerate(zip(scores, features)):
        indices = [np.digitize(f, bin) for f, bin in zip(feature, bins)]
        cur_score = nd_matrix[tuple(indices)]["score"]
        if score > cur_score:
            nd_matrix[tuple(indices)] = {"score": score, "idx": idx}

    return nd_matrix

get_bins(arr, k)

获取分数数组的最小值和最大值之间的等距 bin 阈值。

参数

名称	类型	描述	默认值
arr	ndarray	用于计算 bin 的值列表。	必需
k	int	要创建的 bin 数量。	必需

返回值

类型	描述
list	一个 bin 阈值列表，计算为数组最小值和最大值之间的 k 个等距 bin。

源代码位于 tpot/selectors/map_elites_selection.py

def get_bins(arr, k):
    """
    Get equally spaced bin thresholds between the min and max values for the array of scores.

    Parameters
    ----------
    arr : np.ndarray
        The list of values to calculate the bins for.
    k : int
        The number of bins to create.

    Returns
    -------
    list
        A list of bin thresholds calculated to be k equally spaced bins between the min and max of the array.

    """
    min_vals = np.min(arr, axis=0)
    max_vals = np.max(arr, axis=0)
    [np.linspace(min_vals[i], max_vals[i], k) for i in range(len(min_vals))]

get_bins_quantiles(arr, k=None, q=None)

接受一个矩阵并返回基于分位数的 bin 阈值。

参数

名称	类型	描述	默认值
arr	ndarray	用于计算 bin 的矩阵。	必需
k	int	要创建的 bin 数量。此参数创建 k 个等距分位数。例如，k=3 将在 array([0.25, 0.5 , 0.75]) 创建分位数。	None
q	ndarray	用于 bin 的自定义分位数。此参数根据数据的分位数创建 bin。默认值为 None。	None

源代码位于 tpot/selectors/map_elites_selection.py

def get_bins_quantiles(arr, k=None, q=None):
    """
    Takes a matrix and returns the bin thresholds based on quantiles.

    Parameters
    ----------
    arr : np.ndarray
        The matrix to calculate the bins for.
    k : int, optional
        The number of bins to create. This parameter creates k equally spaced quantiles. 
        For example, k=3 will create quantiles at array([0.25, 0.5 , 0.75]).
    q : np.ndarray, optional
        Custom quantiles to use for the bins. This parameter creates bins based on the quantiles of the data. The default is None.
    """
    bins = []

    if q is not None and k is not None:
        raise ValueError("Only one of k or q can be specified")

    if q is not None:
        final_q = q
    elif k is not None:
        final_q = np.linspace(0, 1, k+2)[1:-1]

    for i in range(arr.shape[1]):
        bins.append(np.quantile(arr[:,i], final_q))
    return bins

manhattan(a, b)

计算两个点之间的曼哈顿距离。

参数

名称	类型	描述	默认值
a	ndarray	第一个点。	必需
b	ndarray	第二个点。	必需

返回值

类型	描述
float	两个点之间的曼哈顿距离。

源代码位于 tpot/selectors/map_elites_selection.py

def manhattan(a, b):
    """
    Calculate the Manhattan distance between two points.

    Parameters
    ----------
    a : np.ndarray
        The first point.
    b : np.ndarray
        The second point.

    Returns
    -------
    float
        The Manhattan distance between the two points.
    """
    return sum(abs(val1-val2) for val1, val2 in zip(a,b))

map_elites_parent_selector(scores, k, n_parents=1, rng=None, manhattan_distance=2, grid_steps=10, bins=None)

用于 map-elites 算法的父代选择算法。首先为每个单元格创建最佳个体的网格，然后根据最佳个体单元格之间的曼哈顿距离选择父代。

参数

名称	类型	描述	默认值
scores	ndarray	分数矩阵，其中第一列是分数，其余列是 map-elites 算法的特征。	必需
k	int	要选择的个体数量。	必需
n_parents	int	每个个体要选择的父代数量。默认值为 1。	1
rng	(int, Generator)	随机数生成器。默认值为 None。	None
manhattan_distance	int	父代之间的最大曼哈顿距离。默认值为 2。如果在该距离内找不到父代，则将距离增加 1，直到找到至少一个其他父代。	2
grid_steps	int	用于自动为每个特征创建 bin 阈值的步数。默认值为 None。	10
bins	list	一个列表的列表，其中包含每个特征（分数除外）的 bin 边缘。默认值为 None。	None

返回值

类型	描述
ndarray	为每个个体选择的父代索引数组

源代码位于 tpot/selectors/map_elites_selection.py

def map_elites_parent_selector(scores,  k, n_parents=1, rng=None, manhattan_distance = 2,  grid_steps= 10, bins=None):
    """
    A parent selection algorithm for the map-elites algorithm. First creates a grid of the best individuals per cell and then selects parents based on the Manhattan distance between the cells of the best individuals.

    Parameters
    ----------
    scores : np.ndarray
        The score matrix, where the first column is the score and the rest are the features for the map-elites algorithm.
    k : int
        The number of individuals to select.
    n_parents : int, optional
        The number of parents to select per individual. The default is 1.
    rng : int, np.random.Generator, optional
        The random number generator. The default is None.
    manhattan_distance : int, optional
        The maximum Manhattan distance between parents. The default is 2. If no parents are found within this distance, the distance is increased by 1 until at least one other parent is found.
    grid_steps : int, optional
        The number of steps to use for each feature to automatically create the bin thresholds. The default is None.
    bins : list, optional
        A list of lists containing the bin edges for each feature (other than the score). The default is None.

    Returns
    -------
    np.ndarray
        An array of indexes of the parents selected for each individual

    """


    if grid_steps is not None and bins is not None:
        raise ValueError("Either grid_steps or bins must be provided but not both")

    rng = np.random.default_rng(rng)
    scores = np.array(scores)
    #create grid

    matrix = create_nd_matrix(scores, grid_steps=grid_steps, bins=bins)

    #return true if cell is not empty
    f = np.vectorize(lambda x: x["idx"] is not None)
    valid_coordinates  = np.array(np.where(f(matrix))).T

    idx_to_coordinates = {matrix[tuple(coordinates)]["idx"]: coordinates for coordinates in valid_coordinates}

    idxes = [idx for idx in idx_to_coordinates.keys()] #all the indexes of best score per cell

    distance_matrix = np.zeros((len(idxes), len(idxes)))

    for i, idx1 in enumerate(idxes):
        for j, idx2 in enumerate(idxes):
            distance_matrix[i][j] = manhattan(idx_to_coordinates[idx1], idx_to_coordinates[idx2])


    parents = []

    for i in range(k):
        #randomly select a cell
        idx = rng.choice(idxes) #select random parent

        #get the distance from this parent to all other parents 
        dm_idx = idxes.index(idx) 
        row = distance_matrix[dm_idx] 

        #get all second parents that are within manhattan distance. if none are found increase the distance
        candidates = []
        while len(candidates) == 0:
            candidates = np.where(row <= manhattan_distance)[0]
            #remove self from candidates
            candidates = candidates[candidates != dm_idx]
            manhattan_distance += 1

            if manhattan_distance > np.max(distance_matrix):
                break

        if len(candidates) == 0:
            parents.append([idx, idx]) #if no other parents are found, select the same parent twice. weird to crossover with itself though
        else:
            this_parents = [idx]
            for p in range(n_parents-1):
                idx2_cords = rng.choice(candidates)
                this_parents.append(idxes[idx2_cords])
            parents.append(this_parents)

    return np.array(parents)

map_elites_survival_selector(scores, k=None, rng=None, grid_steps=10, bins=None)

接受一个分数矩阵，并返回 map-elites 网格中最佳单元格中的个体索引。可以接受 grid_steps 参数以自动创建 bin，也可以接受 bins 参数以手动指定 bin。

参数

名称	类型	描述	默认值
scores	ndarray	分数矩阵，其中第一列是分数，其余列是 map-elites 算法的特征。	必需
k	int	要选择的个体数量。默认值为 None。	None
rng	(int, Generator)	随机数生成器。默认值为 None。	None
grid_steps	int	用于自动为每个特征创建 bin 阈值的步数。默认值为 None。	10
bins	list	一个列表的列表，其中包含每个特征（分数除外）的 bin 边缘。默认值为 None。	None

返回值

类型	描述
ndarray	map-elites 网格中最佳单元格中的个体索引数组（无重复）。

源代码位于 tpot/selectors/map_elites_selection.py

def map_elites_survival_selector(scores,  k=None, rng=None, grid_steps= 10, bins=None):
    """
    Takes a matrix of scores and returns the indexes of the individuals that are in the best cells of the map-elites grid.
    Can either take a grid_steps parameter to automatically create the bins or a bins parameter to specify the bins manually.

    Parameters
    ----------
    scores : np.ndarray
        The score matrix, where the first column is the score and the rest are the features for the map-elites algorithm.
    k : int, optional
        The number of individuals to select. The default is None.
    rng : int, np.random.Generator, optional
        The random number generator. The default is None.
    grid_steps : int, optional
        The number of steps to use for each feature to automatically create the bin thresholds. The default is None.
    bins : list, optional
        A list of lists containing the bin edges for each feature (other than the score). The default is None.

    Returns
    -------
    np.ndarray
        An array of indexes of the individuals in the best cells of the map-elites grid (without repeats).

    """

    if grid_steps is not None and bins is not None:
        raise ValueError("Either grid_steps or bins must be provided but not both")

    rng = np.random.default_rng(rng)
    scores = np.array(scores)
    #create grid

    matrix = create_nd_matrix(scores, grid_steps=grid_steps, bins=bins)
    matrix = matrix.flatten()

    indexes =  [cell["idx"] for cell in matrix if cell["idx"] is not None]

    return np.unique(indexes)